Eugene and big number

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Eugene has to do his homework. But today, he is feeling very lazy and wants to you do his homework. His homework has the following given maths problem.
You are given three integers: A, N, M. You write the number A appended to itself N times in a row. Let's call the resulting big number X. For example, if A = 120, N = 3, then X will be 120120120. Find out the value of X modulo M.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow.
Each test case is described in one line containing three integers: A, N and M as described in the problem statement.
Output
For each test case, output a single line containing an integer denoting the value of X modulo M.
Constraints
 1 ≤ T ≤ 10^{5}
 0 ≤ A ≤ 10^{9}
 1 ≤ N ≤ 10^{12}
 2 ≤ M ≤ 10^{9}
Subtasks
Subtask #1 (15 points):
 0 ≤ A ≤ 100
 1 ≤ N ≤ 10^{5}
Subtask #2 (25 points):
 1 ≤ N ≤ 10^{9}
Subtask #3 (60 points):
 Original constraints
Example
Input: 2 12 2 17 523 3 11 Output: 5 6
Explanation
Example 1: As A = 12, N = 2, X = 1212, 1212 modulo 17 = 5
Example 2. As A = 523, N = 3, X = 523523523, 523523523 modulo 11 = 6
Author:  aangairbender 
Tester:  mgch 
Tags  aangairbender 
Date Added:  5042016 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 