最大因数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。
对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。
现在有 q 组询问,第 i(1<= i <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
【输入描述】
第一行,一个正整数 q,表示询问组数。
接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。
【输出描述】
输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= xi、yi <= 1000。
对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。