← 返回题目列表

Codeforces · 2139/A

A. 枫树和乘法

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

Maple 有两个正整数 $$$a$$$ 和 $$$b$$$。她可以执行以下操作任意次数(可能为零)以使 $$$a$$$ 等于 $$$b$$$:

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

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

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含两个正整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le 1000$$$) - Maple 当前拥有的数字。

输出

对于每个测试用例,输出一个整数,表示 Maple 需要使 $$$a$$$ 等于 $$$b$$$ 的最小操作数。

示例

输入
复制

3
1 2
10 3
1000 1000

输出
复制

1
2
0

注意

在第一个测试用例中,您可以将 $$$a=1$$$ 乘以 $$$2$$$ 以获得 $$$a=b=2$$$。这需要一次操作。

在第二个测试用例中,您可以将 $$$a=10$$$ 乘以 $$$300$$$ 得到 $$$a = 3000$$$,然后将 $$$b=3$$$ 乘以 $$$1000$$$ 得到 $$$b=3000$$$。这需要两次操作。请注意,操作后数字可能会超过 $$$1000$$$。

在第三个测试用例中,$$$a$$$ 和 $$$b$$$ 已经相等,因此不需要任何操作。