最大因数

题目描述

给定一棵有 \(n\) 个结点的有根树，这些结点依次以 \(1, 2, \ldots, n\) 编号，根结点的编号为 \(1\)。对于编号为 \(i\)（\(1 < i \le n\)）的结点，其父结点的编号为 \(i\) 的因数中除 \(i\) 以外最大的因数。现在有 \(q\) 组询问，第 \(i\)（\(1 \le i \le q\)）组询问给定 \(x, y\)，请你求出编号分别为 \(x, y\) 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

输入格式

第一行，一个正整数 \(q\)，表示询问组数。

接下来 \(q\) 行，每行两个正整数 \(x, y\)，表示询问结点的编号。

输出格式

输出共 \(q\) 行，每行一个整数，表示结点 \(x, y\) 之间的距离。

样例

输入样例 1

3
1 3
2 5
4 8

输出样例 1

1
2
1

数据范围

对于所有测试点，保证 \(1 \le q \le 10^4\)，\(1 \le x, y \le 10^6\)。（数据范围由题面字体缺字重建，取保守范围）