背景

GESP六级真题(202506)

描述

给定⼀棵有 $10^9$ 个结点的有根树，这些结点依次以 $1,2,..., 10^9$ 编号，根结点的编号为 1 。对于编号为 $k$（$2 \le k \le 10^9$）的结点，其⽗结点的编号为 $k$ 的因数中除 $k$ 以外最⼤的因数。

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

格式

输入

第⼀⾏，⼀个正整数 $q$ ，表⽰询问组数。

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

输出

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

样例

3
1 3
2 5
4 8

1
2
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.0 s

空间限制：512.0 MB