题目描述
给定一棵有 ( 10^9 ) 个结点的树，结点编号为 ( 1 ) 到 ( 10^9 )，根结点为1。结点 ( k ) 的父结点是 ( k ) 的最大真因数。有 ( q ) 次询问，每次询问两个结点 ( x_i ) 和 ( y_i ) 之间的距离（边数）。

输入格式
第一行：一个正整数 ( q )，表示询问次数。
接下来 ( q ) 行：每行两个整数 ( x_i ) 和 ( y_i )。

输出格式
输出 ( q ) 行，每行一个整数，表示对应询问的距离。

样例1
输入：

3  
2 3  
4 6  
120 650  

输出：

1  
2  
9  

样例2
输入：

1
120 650

输出：

9

数据范围
对于60%的测试点，保证1 ≤ xi, yi ≤ 1000。 对于所有的测试点，保证1 ≤ q ≤ 1000，1 ≤ xi, yi ≤ $10^9$