Potencias

Se le pide escribir un programa para hallarlas potencias. Para esto leerá tres números enteros a,b,m. Le piden hallar a^b % m. Para esto hacemos recuerdo que ((a * b)%m = (a%m * b%m)%m)

Entrada

La primera línea indica el número de casos de prueba. Cada siguiente línea corresponde a un caso de prueba que consiste de tres enteros a,b,m con 1 ≤ a,b,m ≤ 10¹⁷.

Salida

Para cada terna a,b,c imprima en una línea a^b % m.

Ejemplo de Entrada

6
3 2 3  
2 8 5  
2 4 10  
4 4 1000  
1 1 1  
10 10 9

Ejemplo de Salida

0  
1  
6  
256  
0  
1