10719.最⼤因数

给定⼀棵有10⁹个结点的有根树，这些结点依次以1，2，……，10⁹编号，根结点的编号为1。对于编号为k（2≤k≤10⁹）的结点，其⽗结点的编号为k的因数中除k以外最⼤的因数。

现在有 $q$ 组询问，第 $i$（$1 \leq i \leq q$）组询问给定 $x_i, y_i$，请你求出编号分别为 $x_i, y_i$ 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

第⼀⾏，⼀个正整数q，表⽰询问组数。 接下来q⾏，每⾏两个正整数x_iy_i，表⽰询问结点的编号。

输出共q⾏，每⾏⼀个整数，表⽰结点x_iy_i之间的距离。