最大因数

题面描述

给定一棵有 个结点的有根树，这些结点依次以 编号，根结点的编号为 。对于编号为 （）的结点，其父结点的编号为 的因数中除 以外最大的因数。

现在有 组询问，第 （）组询问给定 ，请你求出编号分别为 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

输入格式

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

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

输出格式

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

样例1

输入：

3
1 3
2 5
4 8

输出：

1
2
1

样例2

输入：

1
120 650

输出：

9

数据范围

对于 的测试点，保证 。

对于所有测试点，保证 ，。

时间与内存限制

时间限制：1.0 s

内存限制：512.0 MB