给定两个整数 $a$ 和 $b$，每一轮你可以执行以下两种操作之一：

- 如果 $a > 0$，则将 $a$ 的值减少 $\gcd(a, b)$。
- 如果 $b > 0$，则将 $b$ 的值减少 $\gcd(a, b)$。

Grace 想知道使得 $a$ 和 $b$ 都变为 $0$ 所需的最少轮数。

**注意：** $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。例如，$\gcd(6, 8) = 2$，$\gcd(7, 5) = 1$。$\gcd(x, 0)$ 和 $\gcd(0, x)$ 的值定义为 $x$

每个测试文件包含多个测试用例。第一行包含测试用例的数量 $T$（$1 \le T \le 1000$）。

接下来是测试用例的描述。

每个测试用例占一行，包含两个整数 $a$ 和 $b$（$1 \le a \le b$，$a \le 5000$，$b \le 10^{18}$）。

对于每个测试文件，保证所有测试用例的 $a$ 之和不超过 $10^4$。

对于每个测试用例，输出一个整数，表示使 $a$ 和 $b$ 都变为 $0$ 所需的最少轮数。

**第一个测试用例：** $a = 2, b = 3$

一种最优方案如下：

1. 对 $b$ 操作：$b = 3 - \gcd(2, 3) = 3 - 1 = 2$，状态变为 $(2, 2)$
2. 对 $a$ 操作：$a = 2 - \gcd(2, 2) = 2 - 2 = 0$，状态变为 $(0, 2)$
3. 对 $b$ 操作：$b = 2 - \gcd(0, 2) = 2 - 2 = 0$，状态变为 $(0, 0)$