昨天考试题目，求解法：

有一个题目：有一个 $10^9$ 个结点的有根树，且满足：根节点的编号为 $1$，编号为 $k (2≤k≤10^9)$ 的结点的父结点编号为 $k$ 所有因数中除 $k$ 以外最大的一个。给出 $x,y$，求出编号为 $x$ 的结点与编号为 $y$ 的结点的距离。$q$ 组数据，$1≤q≤1000,1≤x,y≤10^9$。

DeepSeek 给出的解法用到了 LCA，超过六级考纲。求无 LCA 的解法。

输入 1：

3
1 3
2 5
4 8

输出 1：

1
2
1

第二组忘记了。