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 ≤ 105
- 0 ≤ A ≤ 109
- 1 ≤ N ≤ 1012
- 2 ≤ M ≤ 109

-----Subtasks-----
Subtask #1 (15 points):
- 0 ≤ A ≤ 100
- 1 ≤ N ≤ 105

Subtask #2 (25 points):
- 1 ≤ N ≤ 109

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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    s = len(str(a))
    #print(s)
    c = 10**s - 1
    w = c*m
    b = pow(10,n*s,w)-1
    d = b//c
    ans = (d%m)*(a%m)
    print(ans%m)  

for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    print((((pow(10,n*(len(str(a))),(10**(len(str(a))) - 1)*m)-1)//(10**(len(str(a))) - 1))%m)*(a%m)%m)

for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    print((((pow(10,n*(len(str(a))),(10**(len(str(a))) - 1)*m)-1)//(10**(len(str(a))) - 1))%m)*(a%m)%m)

for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    s = len(str(a))
    c = 10**s - 1
    w = c*m
    b = pow(10,n*s,w)-1
    d = b//c
    ans = (d%m)*(a%m)
    print(ans%m)  

import math 

def no(n):
    c=0
    while n>0:
        c += 1
        n //=10
    return c

  
# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
  
  
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
  
    return x 
  
  
# Function to compute a/b under modulo m  
 


for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    if a == 0 :
        s = 1
    else:
        s = no(a)
    #print(s)
    c = 10**s - 1
    w = c*m
    b = pow(10,n*s,w)-1
    d = b//c
    ans = (d%m)*(a%m)
    print(ans%m)  
  
        
    

import math 

def no(n):
    c=0
    while n>0:
        c += 1
        n //=10
    return c

  
# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
  
  
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
  
    return x 
  
  
# Function to compute a/b under modulo m  
 


for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    s = len(str(a))
    #print(s)
    c = 10**s - 1
    w = c*m
    b = pow(10,n*s,w)-1
    d = b//c
    ans = (d%m)*(a%m)
    print(ans%m)  
  
        
    

import math 

def no(n):
    c=0
    while n>0:
        c += 1
        n //=10
    return c

  
# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
  
  
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
  
    return x 
  
  
# Function to compute a/b under modulo m  
 


for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    s = no(a)   
    c = 10**s - 1
    if math.gcd(c,m) == 1:
        b = pow(10,n*s,m)-1
        r = modInverse(c,m)
        d = (b%m)*(r%m)
    else:
        w = c*m
        b = pow(10,n*s,w)-1
        d = b//c
    ans = (d%m)*(a%m)
    print(ans%m)  
  
        
    

import math 

def no(n):
    c=0
    while n>0:
        c += 1
        n //=10
    return c

  
# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
  
  
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
  
    return x 
  
  
# Function to compute a/b under modulo m  
 


for _ in range(int(input())):
    a,n,m = map(int,input().split(' '))
    s = no(a)   
    c = 10**s - 1
    w = c*m
    b = pow(10,n*s,w)-1
    #r = modInverse(c,m)
    d = b//c
    ans = (d%m)*(a%m)
    print(ans%m)  
  
        

import sys
def cal_power(a, n, m):
    if n == 0:
        return 1
    elif n == 1:
        return a % m
    elif not n % 2:
        return ((cal_power(a, n // 2, m) % m)**2) % m
    else:
        return ((a % m) * (((cal_power(a, (n - 1)// 2, m)) % m)**2) % m) % m

def cal(b, n, m):
    if n == 0:
        return 0
    elif n == 1:
        return b % m
    elif not n % 2:
        return (((1 +cal_power(b, n // 2, m)) % m) * (cal(b, n // 2, m) % m)) % m
    else:
        return (((1 + cal_power(b, (n + 1) // 2, m)) % m) * (cal(b, ((n - 1) // 2), m) % m) + cal_power(b, (n + 1) // 2, m) % m) % m

def solve(a, n, m):
    l = len(str(a))
    x = a % m
    q = 10**l % m
    return (x * (1 + cal(q, n - 1, m))) % m

for _ in range(int(input())):
    a,n,m = [int(temp) for temp in input().split()]
    print(solve(a, n, m))