給定三個正整數 $a, b, k$，求 $\text{LCM}(a + x, b + y)$ 的最小值，其中 $x$ 和 $y$ 都是不大於 $k$ 的非負整數。

$\text{LCM}(a, b)$ 表示 $a$ 和 $b$ 的最小公倍數。例如 $\text{LCM}(5, 7) = 35$，$\text{LCM}(10, 6) = 30$。

† 在每個測試文件內，保證至多有 $1$ 組測試數據滿足 $\max(a, b) > 10^5$。

輸入格式

每個測試文件包含多組測試數據。第一行包含測試數據的組數 $T$ ($1 \le T \le 10^4$)。每組測試數據的格式如下：

第一行包含三個整數 $a, b, k$ ($1 \le a, b, k \le 10^{14}$)。

輸出格式

對於每組數據，輸出一行一個整數，表示你的答案。

範例

輸入格式 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