| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 61 | 34 | 33 | 57.895% |
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ドル\le a,b\le 10^{18}$).
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:
She must perform these operations sequentially, but she can perform them any number of times and in any order. She must reach exactly $c$ bales in the first pile and $d$ bales in the second pile (1ドル\le c,d\le 10^{18}$).
For each of $T$ (1ドル\le T\le 10^4$) independent test cases, output the minimum number of operations needed to fulfill the prophecy, or if it is impossible to do so, output -1.
The first line contains $T$.
The next $T$ lines each contain four integers $a,b,c,d$.
Output $T$ lines, the answer to each test case.
4 5 3 5 2 5 3 8 19 5 3 19 8 5 3 5 3
-1 3 -1 0
In the first test case, it is impossible since $b>d$ initially, but operations can only increase $b$.
In the second test case, initially the two piles have $(5, 3)$ bales. Bessie can first increase the first pile by the amount in the second pile, resulting in $(8, 3)$ bales. Bessie can then increase the second pile by the new amount in the first pile, and do this operation twice, resulting in $(8, 11)$ and finally $(8, 19)$ bales. This matches $c$ and $d$ and is the minimum number of operations to get there.
Note that the third test case has a different answer than the second because $c$ and $d$ are swapped (the order of the piles matters).
In the fourth test case, no operations are necessary.
1 1 1 1 1000000000000000000
999999999999999999