给定⼀棵有109个结点的有根树,这些结点依次以1,2,……,109编号,根结点的编号为1。对于编号为k(2≤k≤109)的结点,其⽗结点的编号为k的因数中除k以外最⼤的因数。
现在有 q 组询问,第 i(1≤i≤q)组询问给定 xi,yi,请你求出编号分别为 xi,yi 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
第⼀⾏,⼀个正整数q,表⽰询问组数。 接下来q⾏,每⾏两个正整数xiyi,表⽰询问结点的编号。
输出共q⾏,每⾏⼀个整数,表⽰结点xiyi之间的距离。
3 1 3 2 5 4 8
1 2 1
1 120 650
9