A. 枫树与乘法

每次测试的时间限制：$1$ 秒
每次测试的内存限制：$256$ 兆字节

枫树有两个正整数 $a$ 和 $b$。她可以任意多次（可能为零次）执行以下操作，使得 $a$ 等于 $b$：

• 选择任意正整数 $x$，并将 $a$ 或 $b$ 乘以 $x$。

你的任务是确定使 $a$ 等于 $b$ 所需的最少操作次数。可以证明这是总是可行的。

输入

每个测试包含多个测试用例。
第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。
接下来是每个测试用例的描述。
每个测试用例的第一行（也是唯一一行）包含两个正整数 $a$ 和 $b$（$1 \le a, b \le 1000$）——枫树当前拥有的两个数字。

输出

对于每个测试用例，输出一个整数，表示枫树需要的最少操作次数。

示例

输入

3
1 2
10 3
1000 1000

输出

1
2
0

注释

• 在第一个测试用例中，你可以将 $a = 1$ 乘以 $2$，得到 $a = b = 2$。这只需要 $1$ 次操作。
• 在第二个测试用例中，你可以先将 $a = 10$ 乘以 $300$，得到 $a = 3000$，然后将 $b = 3$ 乘以 $1000$，得到 $b = 3000$。这需要 $2$ 次操作。注意，操作后数字可能超过 $1000$。
• 在第三个测试用例中，$a$ 和 $b$ 已经相等，因此不需要任何操作。