最大因数

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

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