Sú dané čísla $a,b,c$. Zistite aký zvyšok dáva $a^b$ po delení číslom $c$.
V prvom riadku vstupu je číslo $1\leq t \leq 100\,000$: počet otázok. Každý z nasledovných $t$ riadkov obsahuje tri čísla $1 \leq a,b,c \leq 10^9$.
Pre každú trojicu čísel vypíšte $a^b~mod~c$.
3
2 5 7
6 11 4
123 456 100000007
4
0
55947751