Description

有 $T$ 个盒子，每盒子上有一个锁，锁上有两个整数 $a$ 和 $b$。你可以对这个锁做若干次以下 3 种操作：

• $a$ 和 $b$ 分别减去 $1$
• $a$ 和 $b$ 分别增加 $1$
• $a$ 和 $b$ 分别除以它们共同的素数因子

如果 $a$ 或 $b$ 或两者都变为 $1$，盒子就会解锁。请你编写一个程序，计算每个盒子的锁打开的最少步骤数量。

Input Format

第一行输入一个整数 $T(1≤T≤300)$。

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

Output Format

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

5
4 7
9 8
32 84
11 35
2 1

2
7
5
4
0

Hint

对于第一个样例，最优解之一为 $(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)$。