题目描述

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

现有q组询问，第i（1 ≤ i ≤ q）组询问给定x_i, y_i，请求出编号为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 ≤ x_i, y_i ≤ 1000
• 对于所有测试点，保证1 ≤ q ≤ 1000，1 ≤ x_i, y_i ≤ 10^9