Eugene must do his homework, but he is struggling.
He has three integer numbers: A, N, M. He writes number A on the board N times in a row. Let's call the resulting big number X.
Help Eugene find X modulo M.
Input Format
First line contains T, the number of testcases.
Each testcase contains three numbers: A, N, M separated by a single space.
Constraints
Output Format
Print the required answer for each testcase in a new line.
Sample Input
2
12 2 17
523 3 11
Sample Output
5
6
Explanation
First testcase:
A = 12
N = 2
X = 1212
1212 modulo 17 = 5
Second testcase:
A = 523
N = 3
X = 523523523
523523523 modulo 11 = 6