Problems
Bessie the brilliant bovine has discovered a new fascination—mathematical magic! One day, while trotting through the fields of Farmer John’s ranch, she stumbles upon two enchanted piles of hay. The first pile contains a bales, and the second pile contains b bales (1 ≤ a, b ≤ 10¹⁸). Next to the hay, half-buried in the dirt, she discovers an ancient scroll. As she unfurls it, glowing letters reveal a prophecy:
"To fulfill the decree of the Great Grasslands, the chosen one must transform these two humble hay piles into exactly c and d bales—no more, no less."
Bessie realizes she can only perform the following two spells:
Spell 1: Increase the size of the first pile by the amount currently in the second pile.
Spell 2: Increase the size of the second pile by the amount currently in the first pile.
These operations must be performed sequentially, but they can be applied any number of times and in any order. The goal is to reach exactly c bales in the first pile and d bales in the second pile (1 ≤ c, d ≤ 10¹⁸).
For each of T (1 ≤ T ≤ 10⁴) independent test cases, output the minimum number of operations needed to fulfill the prophecy, or output -1 if it is impossible.
Input
The first line contains an integer T.
The next T lines each contain four space-separated integers a, b, c, d.
Output
For each test case, output a single line containing the minimum number of operations needed to fulfill the prophecy, or -1 if it is impossible.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 20 | |
| #2 | 30 | T ≤ 10 and a, b, c, d ≤ 10⁶ |
| #3 | 50 | No additional constraints |
Example #1
4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3
-1
3
-1
0
Test Case 1: With a=5, b=3, c=5, d=2, b is initially greater than d, and since operations can only increase the number of bales, it is impossible to reach the target.
Test Case 2: Starting from (5,3), Bessie can first use Spell 1 to increase the first pile from 5 to 8 (resulting in (8,3)), and then use Spell 2 twice to raise the second pile from 3 to 11 and then to 19. Thus, a total of 3 operations is required.
Test Case 3: For a=5, b=3, c=19, d=8, the target piles are swapped relative to the available operations, making it impossible.
Test Case 4: The initial state (5,3) already matches the target, so 0 operations are needed.
Example #2
1
1 1 1 1000000000000000000
999999999999999999
In this single test case, the initial state is (1,1) and the target is (1, 10¹⁸). Since the first pile is already at the target, Bessie must perform 10¹⁸ - 1 operations to increase the second pile from 1 to 10¹⁸.
You must sign in to write code.