Blitz Division

Task

Alex is passionate about diverse mathematical challenges, and as a gift for you to start the new IIOT season, he gives you three positive integers $A$, $B$ and $K$. He tells you that you must use exactly $K$ increments (i.e., increasing a value by one) on $A$ and $B$, in any way you want. Now, he wants to find the greatest possible value of the greatest common divisor of the two integers obtained after the increments.

For example, if $A = 7$, $B = 11$ and $K = 3$, the answer is $7$, because we can use all $3$ increments on $B$ to make it equal to $14$ and $\gcd(7, 14) = 7$. However, if $A = 18$, $B = 9$ and $K = 3$, the answer is $10$ ($A = 20$, $B = 10$ after incrementing the values $3$ times).

Alex decided to test you on $T$ such triplets. Show Alex that math is your friend as well!

Input data

The first line contains $T$, the number of test cases. Each of the next $T$ lines contains three positive integers, $A$, $B$, and $K$.

Output data

You need to write $T$ lines, each line containing the answer for the corresponding triple of values.

Constraints and clarifications

• $1 \leq T \leq 100$
• $1 \leq A, B, K \leq 10^{9}$

Example

stdin

4
7 11 3
18 9 3
58 38 14
68 94 231

stdout

7
10
22
131

Explanation

The first two triples of the sample case were explained in the statement. For the third triple, you can increment the numbers to $66$ and $44$, respectively. For the last triple, you can increment the numbers to $131$ and $262$, respectively. It can be proved that these values are optimal.