P9849 [ICPC 2021 Nanjing R] Xingqiu's Joke


有 $T$ 个盒子，每盒子上有一个锁，锁上有两个整数 $a$ 和 $b$。你可以对这个锁做若干次以下 3 种操作： - $a$ 和 $b$ 分别减去 $1$ - $a$ 和 $b$ 分别增加 $1$ - $a$ 和 $b$ 分别除以它们共同的素数因子 如果 $a$ 或 $b$ 或两者都变为 $1$，盒子就会解锁。请你编写一个程序，计算每个盒子的锁打开的最少步骤数量。

第一行输入一个整数 $T(1≤T≤300)$。 接下来 $T$ 行，每行输入 $a$ 和 $b$（$1\le a,b\le 10^9$ 且 $a\neq b$），表示每个盒子的锁的信息。

共输出 $T$ 行，每行输出对应盒子解锁的最少步骤。

对于第一个样例，最优解之一为 $(4, 7) \rightarrow (3, 6) \rightarrow (1, 2)$。 对于第二个样例，最优解之一是执行第一类操作 $7$ 次。 对于第三个样例，最优解之一是 $(32, 84) \rightarrow (16, 42) \rightarrow (15, 41) \rightarrow (14, 40) \rightarrow (13, 39) \rightarrow (1, 3)$。 对于第四个样例，最优解之一是 $(11, 35) \rightarrow (12, 36) \rightarrow (6, 18) \rightarrow (2, 6) \rightarrow (1, 3)$。