G. GCD
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Does anyone understand why many problem setters think it is funny to place a GCD-themed problem as problem G?
—Braised-chicken

Given two integers $$$a$$$ and $$$b$$$, you can perform one of the following two operations in each round:

  • If $$$a \gt 0$$$, then reduce the value of $$$a$$$ by $$$\gcd(a, b)$$$ .
  • If $$$b \gt 0$$$, then reduce the value of $$$b$$$ by $$$\gcd(a, b)$$$ .

Grace wants to know the minimum number of rounds needed to make both $$$a$$$ and $$$b$$$ become $$$0$$$.

$$$^{\dagger}$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$. For example, $$$\gcd(6, 8) = 2, \gcd(7, 5) = 1$$$. The values of $$$\gcd(x, 0)$$$ and $$$\gcd(0, x)$$$ are defined as $$$x$$$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 1000$$$). The description of the test cases follows.

Each test case consists of a single line containing two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a \leq b, a \leq 5000, b \leq 10^{18}$$$).

For each test file, it is guaranteed that the sum of $$$a$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, output a single integer representing the minimum number of rounds needed to make both $$$a$$$ and $$$b$$$ become $$$0$$$.

Example
Input
3
3 4
12 20
114 514
Output
3
4
6
Note

For the first test case in the example, one possible optimal solution is:

  • Perform an operation on $$$a$$$: $$$a = 3 - \gcd(3,4) = 2$$$.
  • Perform an operation on $$$a$$$: $$$a = 2 - \gcd(2,4) = 0$$$.
  • Perform an operation on $$$b$$$: $$$b = 4 - \gcd(0,4) = 0$$$.