时间限制：1.0 s 内存限制：512.0 MB

题目描述

给定一棵有 $10^9$ 个结点的有根树，结点编号为 $1,2,\dots,10^9$，根结点编号为1。对于编号为 $k$（$2 \leq k \leq 10^9$）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。

现有 $q$ 组询问，每组给定 $x_i,y_i$，求两个结点在树上的距离（距离定义为连接两结点的简单路径的边数）。

输入格式

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

输出格式

共输出 $q$ 行，每行一个整数，表示对应询问的两结点距离。

样例

输入样例1

3
1 3
2 5
4 8

输出样例1

1
2
1

输入样例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$