Solve the programming task below in a Python markdown code block.
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

$1\leq T\leq200$  
${0}\leq A\leq10^3$  
$0<N<10^{12}$    
$1<M<10^9$    

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