题目描述

给出两个分数 $\dfrac{a}{b}$ 和 $\dfrac{c}{d}$ ，你每次操作能够选择其中一个分数的分子或分母，将其乘上任意一个整数（当然不能对分母乘 $0$）。要求求出能够使两个分数相等的最小操作次数。

输入格式

第一行一个整数 $t(1\leq t\leq 10^4)$，代表有 $t$ 组数据。

以后 $t$ 行，每行四个整数 $a,b,c,d(0\leq a,c\leq 10^9,1\leq b,d\leq 10^9$)，分别代表两个分数的分子和分母。

输出格式

对于每组数据输出一行一个整数，即最小操作数。

样例解释

对于第 $1$ 组数据，将 $c$ 乘上 $2$ 即可。

对于第 $2$ 组数据，两个分数已经相等，无需操作。

对于第 $3$ 组数据，可以将 $a$ 乘上 $4$，将 $b$ 乘上 $3$。两个分数就能够相等($\dfrac{1\cdot 4}{2 \cdot 3}=\dfrac{2}{3}$)。

样例

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
0
2
0
1
1
1
1