← 返回题目列表

Codeforces · 1031/F

F. 熟悉的操作

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

给你两个正整数 $$$a$$$ 和 $$$b$$$。有两种可能的操作:

1. 将其中一个数字乘以某个素数$$$p$$$;
2. 将其中一个数字除以其质因数$$$p$$$。

获得两个除数相同的整数所需的最少运算次数是多少?给你几个这样的对,你需要找到每一对的答案。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 您要查找答案的整数对的数量。

接下来的 $$$t$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$)。

输出

输出 $$$t$$$ 行 — 其中第 $$$i$$$ 行应包含 $$$a_i$$$、$$$b_i$$$ 对的答案。

示例

输入 #1

8
9 10
100 17
220 70
17 19
4 18
32 20
100 32
224 385

输出 #1

1
3
1
0
1
0
1
1

注意

这些是具有相同除数的数字,在示例测试用例中是最佳获得的:

- $$$(27, 10)$$$, 4 个除数
- $$$(100, 1156)$$$, 9 个除数
- $$$(220, 140)$$$, 12 个除数
- $$$(17, 19)$$$, 2 个除数
- $$$(12, 18)$$$, 6 个除数
- $$$(50, 32)$$$, 6 个除数
- $$$(224, 1925)$$$, 12 个除数

请注意,可能存在多个最佳数字对。