Write a program that computes aⁿ mod m for several queries using fast (square-and-multiply) exponentiation, so that exponents up to 10¹⁸ are handled in about 60 steps.
Input. The first line holds the number of queries t (1 ≤ t ≤ 100). Each of the next t lines holds three integers a n m with 0 ≤ a ≤ 10¹⁸, 0 ≤ n ≤ 10¹⁸ and 1 ≤ m ≤ 2 000 000 000. By convention a⁰ = 1 (also when a = 0).
Output. One line per query with the value of aⁿ mod m (a number from 0 to m − 1).
Example.
Input:
3
2 10 1000
3 4 5
7 0 13
Output:
24
1
1
Hints: reduce a modulo m first; reduce after every multiplication; with m ≤ 2·10⁹ the product of two remainders is below 4·10¹⁸ and fits in a long. Remember that 1 mod 1 = 0.