Dla danych trzech dodatnich liczb całkowitych $a, b, k$, znajdź minimalną wartość $\text{LCM}(a + x, b + y)^\dagger$, gdzie $x$ oraz $y$ są nieujemnymi liczbami całkowitymi nieprzekraczającymi $k$.

$^\dagger \text{LCM}(a, b)$ oznacza najmniejszą wspólną wielokrotność liczb $a$ i $b$. Na przykład $\text{LCM}(5, 7) = 35$, $\text{LCM}(10, 6) = 30$.

Wejście

Każdy plik testowy zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 10^4$). Format każdego zestawu danych jest następujący:

Pierwsza linia zawiera trzy liczby całkowite $a, b, k$ ($1 \le a, b, k \le 10^{14}$).

W każdym pliku testowym gwarantuje się, że co najwyżej jeden zestaw danych spełnia warunek $\max(a, b) > 10^5$.

Wyjście

Dla każdego zestawu danych wypisz w osobnej linii jedną liczbę całkowitą, będącą Twoją odpowiedzią.

Przykład

Wejście 1

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

Wyjście 1

8
14
1
10
101
4999999999999900000000000000