← 返回题目列表

Codeforces · 1720/A

A. 布伦卡玩分数

中文机器翻译题面 查看原题

布伦卡来到幼儿园。这个幼儿园很奇怪,所以每个孩子都会收到两个带有整数分子和分母的分数($$$\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}$$$)。