题目描述

给定一棵有 $10^9$ 个结点的有根树，结点依次以 $1,2,dots,10^9$ 编号，根结点编号为 $1$。对于编号为 $k$（$2 \le k\le 10^9$）的结点，其父结点编号为 $k$ 的因数中除 $k$ 以外最大的因数。现在有 $q$ 组询问，每组给定 $x_i,y_i$，请求出这两个结点在树上的距离。

输入格式

第一行输入正整数 $q$。 接下来 $q$ 行，每行输入两个正整数 $x_i,y_i$。

输出格式

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

3
1 3
4 8
2 4

1
1
1

1
120 650

9

数据范围与提示

• 对于 $60$ 的测试点，保证 $1 \le x_i,y_i \le 1000$。
• 对于全部测试点，保证 $1 \le q\le 1000$，$1 \le x_i,y_i \le 10^9$。
• 样例 1 为根据题意重建的有效样例。

来源

GESP 2025 年 06 月 C++ 六级 T2