Burenka Plays with Fractions

Description:

Input:

The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then follow the descriptions of each test case.

The only line of each test case contains four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$0 \leq a, c \leq 10^9$$$, $$$1 \leq b, d \leq 10^9$$$) — numerators and denominators of the fractions given to Burenka initially.

Output:

For each test case print a single integer — the minimal number of claps Burenka needs to make her fractions equal.

Sample Input:

8
2 1 1 1
6 3 2 1
1 2 2 3
0 1 0 100
0 1 228 179
100 3 25 6
999999999 300000000 666666666 100000000
33 15 0 84

Sample Output:

1
0
2
0
1
1
1
1

Note:

In the first case, Burenka can multiply $$$c$$$ by $$$2$$$, then the fractions will be equal.

In the second case, fractions are already equal.

In the third case, Burenka can multiply $$$a$$$ by $$$4$$$, then $$$b$$$ by $$$3$$$. Then the fractions will be equal ($$$\frac{1 \cdot 4}{2 \cdot 3} = \frac{2}{3}$$$).