Даны три положительных целых числа $a, b, k$. Найдите минимальное значение $\text{LCM}(a + x, b + y)^\dagger$, где $x$ и $y$ — неотрицательные целые числа, не превосходящие $k$.

$^\dagger \text{LCM}(a, b)$ обозначает наименьшее общее кратное чисел $a$ и $b$. Например, $\text{LCM}(5, 7) = 35$, $\text{LCM}(10, 6) = 30$.

Входные данные

Каждый файл с тестами содержит несколько наборов входных данных. В первой строке содержится количество наборов данных $T$ ($1 \le T \le 10^4$).

Каждый набор данных состоит из одной строки, содержащей три целых числа $a, b, k$ ($1 \le a, b, k \le 10^{14}$).

В каждом файле с тестами гарантируется, что не более чем для одного набора данных выполняется условие $\max(a, b) > 10^5$.

Выходные данные

Для каждого набора данных выведите одну строку, содержащую одно целое число — ваш ответ.

Примеры

Входные данные 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