最⼤因数

题目描述

给定⼀棵有 个结点的有根树，这些结点依次以 编号，根结点的编号为 。对于编号为 （ ）的结点，其⽗结点的编号为 的因数中除 以外最⼤的因数。 现在有 组询问，第 （ ）组询问给定 ，请你求出编号分别为 的两个结点在这棵树上的距离。 两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

输入格式

第⼀⾏，⼀个正整数 ，表⽰询问组数。 接下来 ⾏，每⾏两个正整数 ，表⽰询问结点的编号。

输出格式

输出共 ⾏，每⾏⼀个整数，表⽰结点 之间的距离。

样例输入 #1

3
1 3
2 5
4 8

样例输出 #1

1
2
1

样例输入 #2

1
120 650

样例输出 #2

9

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。