Given three positive integers $a, b, k$, find the minimum value of $\text{LCM}(a + x, b + y)^\dagger$, where $x$ and $y$ are non-negative integers not exceeding $k$.

$^\dagger \text{LCM}(a, b)$ denotes the least common multiple of $a$ and $b$. For example, $\text{LCM}(5, 7) = 35$, $\text{LCM}(10, 6) = 30$.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^4$). Each test case consists of a single line containing three integers $a, b, k$ ($1 \le a, b, k \le 10^{14}$).

In each test file, it is guaranteed that at most 1 test case satisfies $\max(a, b) > 10^5$.

Output

For each test case, output a single integer on a new line representing your answer.

Examples

Input 1

6
3 8 4
13 7 4
1 1 1
4 9 2
2 101 100
99999999999998 100000000000000 1

Output 1

8
14
1
10
101
4999999999999900000000000000