#PU1501. USACO 2025 February Contest, Platinum — Problem 2. Transforming Pairs

USACO 2025 February Contest, Platinum — Problem 2. Transforming Pairs

USACO 2025 February Contest, Platinum — Problem 2. Transforming Pairs

题目描述

Answer QQ (1≤Q≤1051\le Q\le 10^5) independent queries each of the following form: You are given four integers a,b,c,da,b,c,d (−1018≤a,b,c,d≤1018-10^{18}\le a,b,c,d\le 10^{18}). In one operation you can either do a+=ba\mathrel{+}=b, or b+=ab\mathrel{+}=a. Determine the minimum number of operations to transform (a,b)(a,b) into (c,d)(c,d), or if it is impossible to do so, output −1-1.

输入格式

The first line contains QQ. The next QQ lines each contain four integers a,b,c,da,b,c,d.

输出格式

The answer for each query on a separate line.

数据范围

(见题面原文)

样例

样例 1

4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3
2
-1
3
0
First query: $(5,-3)\to (2,-3)\to (-1,-3)$
Second query: Impossible.
Third query: $(5,3) \to (8, 3) \to (8, 11) \to (8, 19)$
Fourth query: No operations necessary.