This question consists of T test cases. Each test case consists of three integers A, B and M. For each test case, we wish to know the value of AB (mod M).
Input
The first line will contain one integer T (1 ≤ T ≤ 100,000).
Each of the next T lines will contain three integers A, B and M (1 ≤ A, B, M ≤ 1,000,000).
Output
For each of the T test cases, output a single line containing one integer, the value of AB (mod M).
Sample Input 1
4
5 2 100
5 2 24
2 10 1000
2 10 10000
Sample Output 1
25
1
24
1024