Burenka Plays with Fractions solution codeforces

Burenka Plays with Fractions solution codeforces

Burenka came to kindergarden. This kindergarten is quite strange, so each kid there receives two fractions (𝑎𝑏ab and 𝑐𝑑cd) with integer numerators and denominators. Then children are commanded to play with their fractions.

Burenka is a clever kid, so she noticed that when she claps once, she can multiply numerator or denominator of one of her two fractions by any integer of her choice (but she can’t multiply denominators by 00). Now she wants know the minimal number of claps to make her fractions equal (by value). Please help her and find the required number of claps!

Input

The first line contains one integer 𝑡t (1𝑡1041≤t≤104) — 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𝑎,𝑐1090≤a,c≤1091𝑏,𝑑1091≤b,d≤109) — numerators and denominators of the fractions given to Burenka initially.

Burenka Plays with Fractions solution codeforces

Output

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

Example
input
Copy
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
output
Copy
1
0
2
0
1
1
1
1

Burenka Plays with Fractions solution codeforces

Note

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

In the second case, fractions are already equal.

In the third case, Burenka can multiply 𝑎a by 44, then 𝑏b by 33. Then the fractions will be equal (1423=231⋅42⋅3=23).

 

Leave a Comment