A67436. 最大因数

试题名称：最大因数

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

给定一棵有 10⁹个结点的有根树，这些结点依次以1,2,....10⁹ 编号，根结点的编号为 1。对于编号为 k（2<=k<=10⁹）的结点，其父结点的编号为 k的因数中除 k以外最大的因数。

现在有 q组询问，第 i（1<=i<=q ）组询问给定x_i,y_i ，请你求出编号分别为 x_i,y_i 的两个结点在这棵树上的距离。

两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

3.2.2 输入格式

第一行，一个正整数 q，表示询问组数。

接下来 q行，每行两个正整数 x_i,y_i ，表示询问结点的编号。

3.2.3 输出格式

输出共 q 行，每行一个整数，表示结点 x_i,y_i 之间的距离。

3.2.4 样例

3.2.4.1 输入样例 1

3

1 3

2 5

4 8

3.2.4.2 输出样例 1

1

2

1

3.2.4.3 输入样例 2

1 

120

650

3.2.4.4 输出样例 2

9

3.2.5 数据范围