Mathematical Magic of Hay Stacks

Bessie, the clever cow, has discovered a new obsession – mathematical magic! While galloping on Farmer John's pasture, she found two piles of magical hay. The first pile has $a$ bundles of hay and the second one has $b$ bundles of hay, where \(1 \le a,b \le 10^{18}\).

Beside the hay piles, partly buried in the soil, she discovered an ancient scroll. When she unfurled it, glowing letters revealed a prophecy:

"By the decree of the Great Prairie, the chosen one must transform these ordinary hay piles to exactly \(c\) and \(d\) bundles respectively – not one more or less."

Bessie realizes that she can only cast the following two spells:

• She can cast a spell to increase the first hay pile by the current size of the second pile (i.e. add \(b\) bundles to the first pile).
• She can cast a spell to increase the second hay pile by the current size of the first pile (i.e. add \(a\) bundles to the second pile).

She may cast these spells in any order and any number of times, but she must exactly reach \(c\) bundles in the first pile and \(d\) bundles in the second pile (with \(1 \le c,d \le 10^{18}\)).

For each of \(T\) independent test cases, output the minimum number of spells required to fulfill the prophecy, or -1 if it is impossible.

Note: The spells affect the piles in a way that the greatest common divisor (gcd) of the two pile counts remains invariant. For a valid transformation, it is necessary that \(\gcd(a,b)=\gcd(c,d)\), and of course, \(c \ge a\) and \(d \ge b\).

inputFormat

The first line contains a single integer \(T\) (\(1\le T\le 10^4\)), the number of test cases. Each of the next \(T\) lines contains four space-separated integers \(a\), \(b\), \(c\), and \(d\) (\(1\le a,b,c,d\le 10^{18}\)).

outputFormat

For each test case, output a single line containing the minimum number of spells required to reach exactly \(c\) and \(d\) bundles, or -1 if it is impossible.

sample

1
1 1 3 2

2