20043 - GCD

给定两个整数 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)