布伦卡来到幼儿园。这个幼儿园很奇怪,所以每个孩子都会收到两个带有整数分子和分母的分数($$$\frac{a}{b}$$$ 和 $$$\frac{c}{d}$$$)。然后孩子们被要求玩他们的分数。
Burenka 是一个聪明的孩子,所以她注意到,当她鼓掌一次时,她可以将两个分数之一的分子或分母乘以她选择的任何整数(但她不能将分母乘以 $$$0$$$)。现在她想知道使她的分数相等(按值)的最少拍手次数。请帮助她找到所需的拍手次数!
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后遵循每个测试用例的描述。
每个测试用例的唯一行包含四个整数 $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ ($$$0 \leq a, c \leq 10^9$$$, $$$1 \leq b, d \leq 10^9$$$) — 分数的分子和分母布伦卡最初。
输出
对于每个测试用例,打印一个整数 - Burenka 需要使她的分数相等的最少拍手次数。
示例
输入 #1
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
输出 #1
1 0 2 0 1 1 1 1
注意
在第一种情况下,Burenka 可以将 $$$c$$$ 乘以 $$$2$$$,然后分数将相等。
在第二种情况下,分数已经相等。
在第三种情况下,Burenka 可以将 $$$a$$$ 乘以 $$$4$$$,然后将 $$$b$$$ 乘以 $$$3$$$。那么分数将相等 ($$$\frac{1 \cdot 4}{2 \cdot 3} = \frac{2}{3}$$$)。