Reus recientemente aprendio la operacion xor, lo unico que el recuerda es que es verdad cuando una de las dos afirmaciones es correcta.

Reus se puso a recordar en un problema que habia leido anteriormente, en donde nos daban, 2 numeros (a, b) y teniamos que encontrar la posicion k-esima del numero mas pequeño que solo puede ser dividido por (a o b) pero no por ambos.

Por ejemplo si los numeros $a$=2 y $b$=3, queremos hallar la posicion k=7.

La lista de numeros que solo pueden ser divididos por a o b es:

2, 3, 4, 8, 9, 10, 14, 15, 16, 20, 21, ...

Entonces la respuesta seria 14.

Como tu eres un excelente programador te pide ayuda para resolver este problema.

La primera linea de entrada contiene un numero $t$ $(1 \leq t \leq 10^5)$ que es el numero de casos de prueba.

Las siguientes $t$ lineas contienen 3 enteros $a$, $b$, $k$ $(1 \leq a,b \leq 10^8)$ $a!=b$ y $(1 \leq k \leq 10^{18})$ 

Por cada caso de prueba imprimir el número en la k-esima posición del numero mas pequeño que puede ser dividido por a o b, pero no por ambos.