2321: 最大因数（2025年6月C++六级）
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：34
Solved：21
Description
给定一棵有10^9个节点的有根树，这些节点依次以1, 2, 3, ... 10^9进行编号。对于编号为k（1<=k<=10^9）的节点，其父节点的编号为k的因数中除k以外的最大因数。
现有q组询问，第i（1<=i<=q）组询问给定Xi, Yi，请你求出编号分别为Xi, Yi 的两个节点在这棵树上的距离。两个节点之间的距离是连接这两个节点的简单路径所包含的边数。
Input
第一行，包含一个正整数q，表示询问的组数。
接下来q行，每行两个正整数 Xi, Yi , 表示询问节点的编号。
Output
输出共q行，每行一个整数，表示节点 Xi, Yi 之间的距离。
Sample Input Copy
3
1 3
2 5
4 8Sample Output Copy
1
2
1HINT
【输入样例2】
1
120 650
【输出样例2】
9
1
120 650
【输出样例2】
9
