#G1118. [GESP202506 六级] 最大因数
[GESP202506 六级] 最大因数
[GESP202506 六级] 最大因数
时间限制:1.0 s
内存限制:512.0 MB
题目描述
给定一棵有 个结点的有根树,这些结点依次以 编号,根结点的编号为 。对于编号为 ()的结点,其父结点的编号为 的因数中除 以外最大的因数。
现在有 组询问,第 ()组询问给定 ,请你求出编号分别为 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
输入格式
第一行,一个正整数 ,表示询问组数。
接下来 行,每行两个正整数 ,表示询问结点的编号。
输出格式
输出共 行,每行一个整数,表示结点 之间的距离。
样例 #1
样例输入 #1
3
1 3
2 5
4 8
样例输出 #1
1
2
1
样例 #2
样例输入 #2
1
120 650
样例输出 #2
9
数据范围
| 测试点占比 | 约束 |
|---|---|
| 60% | |
| 100% | , |