题目描述

有两个不等的数 $a$ 和 $b$，你每次操作可以做下面三件事之一：

1. $a \leftarrow a − 1, b \leftarrow b − 1$；

2. $a \leftarrow a + 1, b \leftarrow b + 1$；

3. 任取一个 $a$ 和 $b$ 的公共质因子 $g$，并将 $a$, $b$ 同时除以 $g$。

问至少多少次操作使得 $a, b$ 中至少一个变成 $1$。

输入格式

第一行一个整数 $T$。

接下来 $T$ 行，每行两个整数 $a, b$ 表示一次询问。

输出格式

输出 $T$ 行，每行一个整数表示这次询问最少的操作次数。

样例 1 输入

4
9 8
114 514
2022 504
11 35

样例 1 输出

7
7
4
4

数据范围

子任务 1（20 分）: $1 \le a, b \le 5, 1 \le T \le 100$。

子任务 2（30 分）: $1 \le a, b \le 1000, 1 \le T \le 100$。

子任务 3（50 分）: $1 \le a, b \le 10^9, 1 \le T \le 100$。