Minimal Operations Transformation

You are given Q independent queries. In each query, you are given four integers \(a\), \(b\), \(c\), and \(d\) (\( -10^{18} \le a,b,c,d \le 10^{18} \)). In one operation, you can perform one of the following:

• \( a \mathrel{+}= b \)
• \( b \mathrel{+}= a \)

Your task is to transform the pair \((a, b)\) into \((c, d)\) with a minimum number of operations. If it is impossible to complete the transformation, output \(-1\).

Note: One may prove that if the transformation is possible then the greatest common divisor of \(a\) and \(b\) is invariant, that is, \(\gcd(a,b) = \gcd(c,d)\) (with the convention \(\gcd(0,0)=0\)).

inputFormat

The first line contains an integer \(Q\) (\(1 \le Q \le 10^5\)), the number of queries. Each of the next \(Q\) lines contains four space‐separated integers: \(a\), \(b\), \(c\), and \(d\).

outputFormat

For each query, output a single integer representing the minimum number of operations needed to transform \((a, b)\) into \((c, d)\), or \(-1\) if the transformation is impossible.

sample

3
1 1 5 2
4 -3 1 -3
-2 3 1 3

3
1
-1