3つの正整数 $a, b, k$ が与えられます。$x$ および $y$ がいずれも $k$ 以下の非負整数であるとき、$\text{LCM}(a + x, b + y)^\dagger$ の最小値を求めてください。

$^\dagger \text{LCM}(a, b)$ は $a$ と $b$ の最小公倍数を表します。例えば、$\text{LCM}(5, 7) = 35$、$\text{LCM}(10, 6) = 30$ です。

入力

各テストファイルには複数のテストケースが含まれます。1行目にテストケースの数 $T$ ($1 \le T \le 10^4$) が与えられます。各テストケースの形式は以下の通りです。

1行目に3つの整数 $a, b, k$ ($1 \le a, b, k \le 10^{14}$) が与えられます。

各テストファイルにおいて、$\max(a, b) > 10^5$ を満たすテストケースは最大で1つであることが保証されています。

出力

各テストケースについて、答えを1行に出力してください。

入出力例

入力 1

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

出力 1

8
14
1
10
101
4999999999999900000000000000