给你两个正整数 $$$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 个除数
请注意,可能存在多个最佳数字对。