Description
## 题目描述
给定一棵有 $10^9$ 个结点的有根树，这些结点依次以 $1, 2, \dots, 10^9$ 编号，根结点的编号为 $1$。对于编号为 $k$（$2 \leq k \leq 10^9$）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。
现在有 $q$ 组询问，第 $i$（$1 \leq i \leq q$）组询问给定 $x_i, y_i$，请你求出编号分别为 $x_i, y_i$ 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
## 输入格式
第一行，一个正整数 $q$，表示询问组数。
接下来 $q$ 行，每行两个正整数 $x_i, y_i$，表示询问结点的编号。
## 输出格式
输出共 $q$ 行，每行一个整数，表示结点 $x_i, y_i$ 之间的距离。
## 输入输出样例 #1
### 输入 #1
```
3
1 3
2 5
4 8
```
### 输出 #1
```
1
2
1
```
## 输入输出样例 #2
### 输入 #2
```
1
120 650
```
### 输出 #2
```
9
```
## 说明/提示
对于 $60\%$ 的测试点，保证 $1 \leq x_i, y_i \leq 1000$。
对于所有测试点，保证 $1 \leq q \leq 1000$，$1 \leq x_i, y_i \leq 10^9$。
