行秋又一次把重云的冰棍藏进了一个带有奇怪锁的盒子里。璃月的夏天总是非常炎热，而重云因为体内过剩的阳气而倍感煎熬，所以他迫切地需要那根冰棍。

Pixiv ID: 86787400

锁上有两个整数 $a$ 和 $b$。重云可以进行任意次数的以下三种操作：

• 将 $a$ 和 $b$ 同时减 1；
• 将 $a$ 和 $b$ 同时加 1；
• 将 $a$ 和 $b$ 同时除以它们的一个公共质因数（即除以一个质数 $g$，使得 $a$ 和 $b$ 都能被 $g$ 整除）。

如果 $a$ 或 $b$（或者两者）变为 1，盒子就会被解锁。为了帮助重云尽快拿回冰棍，请告诉他解锁盒子所需的最少操作次数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 300$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le 10^9, a \neq b$)。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示使 $a$ 或 $b$（或两者）等于 1 所需的最少操作次数。

样例

输入 1

5
4 7
9 8
32 84
11 35
2 1

输出 1

2
7
5
4
0

说明

对于第一个样例，最优方案是 $(4, 7) \to (3, 6) \to (1, 2)$。

对于第二个样例，最优方案是执行 7 次第一种操作。

对于第三个样例，最优方案是 $(32, 84) \to (16, 42) \to (15, 41) \to (14, 40) \to (13, 39) \to (1, 3)$。

对于第四个样例，最优方案是 $(11, 35) \to (12, 36) \to (6, 18) \to (2, 6) \to (1, 3)$。