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 XmoduloM.
First line contains T, the number of testcases.
Each testcase contains three numbers: A, N, M separated by a single space.
Print the required answer for each testcase in a new line.
12 2 17
523 3 11
First testcase: A = 12 N = 2 X = 1212
1212 modulo 17 = 5
Second testcase: A = 523 N = 3 X = 523523523
523523523 modulo 11 = 6