H. Abushogi Server Management
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi is managing two legacy servers with data integrity levels $$$a$$$ and $$$b$$$.

He has a synchronization token with power $$$c$$$. His goal is to make the integrity levels of both servers exactly equal ($$$a = b$$$) using the minimum number of operations.

In one operation, Abushogi can choose to do exactly one of the following:

  • Sync: Update $$$a$$$ to $$$\gcd(a, c)$$$ and update $$$b$$$ to $$$\gcd(b, c)$$$ simultaneously;
  • Upgrade: Increment the power of her token $$$c$$$ by $$$1$$$ ($$$c = c + 1$$$).

Output the minimum number of operations needed to make $$$a$$$ and $$$b$$$ equal.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le T \le 10^5$$$) — denotes the number of test cases.

Each test case consists of a single line containing three integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a, b, c \le 10^{18}$$$) — denotes the data integrity levels and the power.

Output

For each testcase, output a single integer: the minimum number of operations required to make $$$a$$$ and $$$b$$$ equal.

Example
Input
4
10 10 5
10 15 5
6 10 15
6 35 14
Output
0
1
2
3