给定一棵有 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 之间的距离。

对于 60% 的测试点，保证 1≤xi,yi≤1000。

对于所有测试点，保证 1≤q≤1000，1≤xi,yi≤10^9。