Codeforces Round 1048 (Div. 2)

A. 枫叶与乘法 (Maple and Multiplication)

时间限制： 1 秒 内存限制： 256 MB

题目描述

枫叶 (Maple) 有两个正整数 a 和 ​b​。 她可以执行任意次数（可能为零）的以下操作，使 a 变为 ​b​：

• 选择任意一个正整数 ​x​，然后将 a 或 b 乘以 ​x​。

请你计算：使 a 等于 b 所需的最少操作次数。 可以证明，这总是可行的。

输入格式

每个测试包含多个测试用例。 第一行输入一个整数 t (1 ≤ t ≤ 100)，表示测试用例的个数。

接下来每个测试用例一行，包含两个正整数 a, b (1 ≤ a, b ≤ 1000) —— Maple 当前拥有的两个数。

输出格式

对于每个测试用例，输出一个整数，表示 Maple 将 a 变为 b 所需的最少操作次数。

样例输入

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 已经相等，不需要任何操作。