문제

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 can magically conjure new bales to increase the first pile’s size by the amount currently in the second pile.She can magically conjure new bales to increase the second pile’s size by the amount currently in the first pile. 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.

예제 입력 1

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

예제 출력 1

-1
3
-1
0

예제 입력 2

1
1 1 1 1000000000000000000

예제 출력 2

999999999999999999

점수

Inputs 3-4: $\max(c, d) \le 20 \cdot\min(a, b)$ Inputs 5-7: $T \le 10$ and $a,b,c,d\le 10^6$ Inputs 8-12: No additional constraints