Problems
Answer Q independent queries each of the following form.
You are given four integers a, b, c, d (−10¹⁸ ≤ a, b, c, d ≤ 10¹⁸). In one operation, you can either perform:
Operation 1: a += b.
Operation 2: b += a.
Determine the minimum number of operations required to transform the pair (a, b) into (c, d). If it is impossible, output −1.
Input
The first line contains an integer Q (1 ≤ Q ≤ 10⁵).
The next Q lines each contain four space-separated integers a, b, c, d (−10¹⁸ ≤ a, b, c, d ≤ 10¹⁸).
Output
Output Q lines, where the i-th line contains the minimum number of operations required to transform (a, b) into (c, d) for the i-th query, or −1 if it is impossible.
Example
4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3
2
-1
3
0
For the first query, starting from (5, −3): performing Operation 1 yields (5 + (−3), −3) = (2, −3), and a second Operation 1 yields (2 + (−3), −3) = (−1, −3). Hence, 2 operations are needed.
For the second query, it is impossible to transform (5, 3) into (5, 2).
For the third query, (5, 3) transforms as follows: (5, 3) → (5 + 3, 3) = (8, 3) → (8, 3 + 8) = (8, 11) → (8, 11 + 8) = (8, 19), requiring 3 operations.
For the fourth query, (5, 3) is already (5, 3), so 0 operations are needed.
You must sign in to write code.