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

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
T = int(input())

def S(A, l, N, M):
	if N == 0:
		return A % M
	if N % 2 == 0:
		return (S(A, l, N - 1, M) * l + S(A, l, 0, M)) % M
	z = S(A, l, N // 2, M)
	return z * (pow(l, N // 2 + 1, M) + 1) % M

def S1(A, N, M):
	return S(A, 10 ** len(str(A)), N - 1, M)
for t in range(T):
	(A, N, M) = list(map(int, input().split()))
	print(S1(A, N, M))


def expMod(base, exp, M):
	if exp == 0:
		return 1
	rest = expMod(base * base % M, exp // 2, M)
	return (base if exp % 2 else 1) * rest % M

def repeatMod(A, N, M):
	if N == 1:
		return A % M
	n = len(str(A))
	rest = (expMod(10, N // 2 * n, M) + 1) * repeatMod(A, N // 2, M) % M
	if N % 2:
		return (A + 10 ** n * rest) % M
	else:
		return rest
num_cases = int(input())
for case in range(num_cases):
	(A, N, M) = map(int, input().split())
	print(repeatMod(A, N, M))


for t in range(int(input())):
	(a, n, m) = map(int, input().split())
	d = 1
	if a > 9:
		if a < 100:
			d = 2
		elif a < 1000:
			d = 3
		else:
			d = 4
	m *= 10 ** d - 1
	ans = (pow(10, n * d, m) - 1) * (a % m) % m
	print(ans // (10 ** d - 1))


def num_mod(a, n, m):
	if a == 0:
		return 0
	if n <= 1:
		return n
	half = num_mod(a, n // 2, m)
	l = len(str(a))
	return (pow(10, l * (n - 1), m) * (n % 2) + half * (pow(10, l * (n // 2), m) + 1)) % m
for _ in range(int(input())):
	(a, n, m) = map(int, input().split())
	print(num_mod(a, n, m) * a % m)


def geom(a, k, n):
	if k <= 2:
		return sum((a ** i for i in range(k))) % n
	else:
		m = k // 2
		b = pow(a, 2, n)
		g = (1 + a) * geom(b, m, n) % n
		return g if k % 2 == 0 else (g + pow(a, k - 1, n)) % n

def f(a, m, n):
	k = len(str(a))
	r = 10 ** k
	return a * geom(r, m, n) % n
n = int(input().strip())
a = []
for a_i in range(n):
	(a, m, n) = [int(a_temp) for a_temp in input().strip().split(' ')]
	t = f(a, m, n)
	print(t)


m = int(1000000000.0) + 7

def mul(a, b):
	c0 = a[0] * b[0] + a[1] * b[2]
	c1 = a[0] * b[1] + a[1] * b[3]
	c2 = a[2] * b[0] + a[3] * b[2]
	c3 = a[2] * b[1] + a[3] * b[3]
	if c0 < 0 or c0 >= m:
		c0 %= m
	if c1 < 0 or c1 >= m:
		c1 %= m
	if c2 < 0 or c2 >= m:
		c2 %= m
	if c3 < 0 or c3 >= m:
		c3 %= m
	return (c0, c1, c2, c3)

def matpow(mat, n):
	res = (1, 0, 0, 1)
	while n:
		if n & 1:
			res = mul(res, mat)
		mat = mul(mat, mat)
		n >>= 1
	return res

def solve(a, n, m):
	p = 1
	while p <= a:
		p *= 10
	p %= m
	tran = (p + 1, -p, 1, 0)
	ptran = matpow(tran, n - 1)
	f = (ptran[2] * (p + 1) + ptran[3]) % m
	res = f * a % m
	return res % m
for t in range(int(input())):
	(a, n, m) = map(int, input().split())
	res = solve(a, n, m)
	print(res)


from math import log10

def geo_sum_mod(r, n, m):
	if n == 0:
		return 1
	if n % 2 == 1:
		return (1 + r) * geo_sum_mod(r * r % m, (n - 1) // 2, m) % m
	return (1 + r * ((1 + r) * geo_sum_mod(r * r % m, n // 2 - 1, m)) % m) % m

def main():
	T = int(input())
	for _ in range(T):
		(A, N, M) = map(int, input().split())
		if A == 0:
			print(0)
		else:
			print(A * geo_sum_mod(pow(10, int(log10(A)) + 1, M), N - 1, M) % M)
main()


T = int(input())
for t in range(T):
	(A, N, M) = map(int, input().split())
	B = pow(10, len(str(A)), M)
	C = 0
	D = 1
	while N:
		if N & 1:
			C = (C + A * D) % M
			D = D * B % M
		A = (A + A * B) % M
		B = B * B % M
		N >>= 1
	print(C)


def helper(k, n, m):
	x = 1
	if n < 2:
		return x
	if n % 2 == 0:
		return (pow(10, k, m) + 1) * helper(2 * k, n // 2, m)
	else:
		return pow(10, k, m) * helper(k, n - 1, m) + 1

def process(a, n, m):
	k = len(str(a))
	a %= m
	x = helper(k, n, m)
	return a * x % m
for _ in range(int(input())):
	(a, n, m) = map(int, input().split())
	print(process(a, n, m))


def f(a, n, m):
	if n == 1:
		return a % m
	half = f(a, n // 2, m)
	la = len(str(a))
	h = n // 2
	if n % 2 == 0:
		return (half * pow(10, h * la, m) + half) % m
	return (half * pow(10, h * la + la, m) + half * 10 ** la + a) % m
for _ in range(int(input())):
	(a, n, m) = [int(x) for x in input().split()]
	print(f(a, n, m))


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def gcd_matrix(a, b):
	M = [[1, 0, a], [0, 1, b]]
	if a > 0 and b > 0:
		while M[0][2] != 0 and M[1][2] != 0:
			if M[0][2] > M[1][2]:
				multiple = M[0][2] // M[1][2]
				for i in range(0, 3):
					M[0][i] -= multiple * M[1][i]
			elif M[0][2] < M[1][2]:
				multiple = M[1][2] // M[0][2]
				for i in range(0, 3):
					M[1][i] -= multiple * M[0][i]
			elif M[0][2] == M[1][2]:
				return M[0][2]
		if M[0][2] == 0:
			return M[1][2]
		else:
			return M[0][2]
	elif a != 0 and b != 0:
		return gcd_matrix(abs(a), abs(b))
	else:
		return 0

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def is_miller_rabin(x, num_tests=3):
	k = x - 1
	e = 0
	while k % 2 == 0:
		e += 1
		k //= 2
	tests = [False for _ in range(0, num_tests)]
	A = [2, 3, 5]
	for j in range(3, num_tests):
		A.append(random.randint(7, x - 1))
	if x < 2047:
		num_tests = 1
	elif x < 1373653:
		num_tests = 2
	elif x < 25326001:
		num_tests = 3
	for i in range(0, num_tests):
		ak = pow_mod(A[i], k, x)
		if ak == 1:
			tests[i] = True
		else:
			for j in range(0, e):
				if ak == x - 1:
					tests[i] = True
				ak = ak * ak % x
	for i in range(0, num_tests):
		if not tests[i]:
			return False
	return True

def factor(n, PL):
	sqrt = int(pow(n, 0.5)) + 1
	factor_list = []
	if not PL:
		PL = prime_list(sqrt)
	for p in PL:
		if n % p == 0:
			elet = [p, 0]
			while not n % p:
				n //= p
				elet[1] += 1
			factor_list.append(elet)
	if n != 1:
		if is_miller_rabin(n):
			factor_list.append([n, 1])
	return factor_list

def euler_totient_with_factors(n, factors):
	for ar_elet in factors:
		n //= ar_elet[0]
		n *= ar_elet[0] - 1
	return n
T = int(input())
PL = prime_list(32000)
for _ in range(0, T):
	(A, N, M) = [int(a) for a in input().split()]
	FL = factor(M, PL)
	totient_m = euler_totient_with_factors(M, FL)
	B = A
	if A == 0:
		print(0)
	else:
		d = 0
		while B > 0:
			B //= 10
			d += 1
		b = pow(10, d) - 1
		ten_power = pow_mod(10, d * N, b * M) - 1
		binverse = 1
		if d == 1:
			if M % 9 == 0:
				if ten_power % 9 == 0:
					ten_power //= 9
				elif ten_power % 3 == 0:
					ten_power //= 3
			elif M % 3 == 0:
				if ten_power % 9 == 0:
					ten_power //= 9
				elif ten_power % 3 == 0:
					ten_power //= 3
			else:
				binverse = pow_mod(b, totient_m - 1, b * M)
		elif d == 2:
			if M % 3 == 0 and M % 11 == 0:
				if ten_power % 9 == 0 and ten_power % 11 == 0:
					ten_power //= 99
				elif ten_power % 9 == 0:
					ten_power //= 9
				elif ten_power % 3 == 0 and ten_power % 11 == 0:
					ten_power //= 33
				elif ten_power % 3 == 0:
					ten_power //= 3
				binverse = 1
			elif M % 3 == 0:
				if ten_power % 9 == 0:
					ten_power //= 9
				elif ten_power % 3 == 0:
					ten_power //= 3
				binverse = pow_mod(11, totient_m - 1, b * M)
			elif M % 11 == 0:
				if ten_power % 11 == 0:
					ten_power //= 11
				binverse = pow_mod(9, totient_m - 1, b * M)
			else:
				binverse = pow_mod(b, totient_m - 1, b * M)
		elif d == 3:
			if M % 3 == 0 and M % 37 == 0:
				if ten_power % 999 == 0:
					ten_power //= 999
				elif ten_power % 37 == 0 and ten_power % 9 == 0:
					ten_power //= 9
					ten_power //= 37
				elif ten_power % 37 == 0 and ten_power % 3 == 0:
					ten_power //= 3
					ten_power //= 37
				elif ten_power % 27 == 0:
					ten_power //= 27
				elif ten_power % 9 == 0:
					ten_power // 9
				elif ten_power % 3 == 0:
					ten_power //= 3
				b_inverse = 1
			elif M % 3 == 0:
				if ten_power % 27 == 0:
					ten_power //= 27
				elif ten_power % 9 == 0:
					ten_power //= 9
				elif ten_power % 37 == 0 and ten_power % 3 == 0:
					ten_power //= 3
				binverse = pow_mod(37, totient_m - 1, b * M)
			elif M % 37 == 0:
				if ten_power % 37 == 0:
					ten_power //= 37
				binverse = pow_mod(27, totient_m - 1, b * M)
			else:
				binverse = pow_mod(b, totient_m - 1, b * M)
		elif d == 4:
			div_3 = False
			div_11 = False
			div_101 = False
			if M % 3 == 0:
				div_3 = True
				if ten_power % 9 == 0:
					ten_power //= 9
				elif ten_power % 3 == 0:
					ten_power //= 3
			if M % 11 == 0:
				div_11 = True
				if ten_power % 11 == 0:
					ten_power //= 11
			if M % 101 == 0:
				div_101 = True
				if ten_power % 101 == 0:
					ten_power //= 101
			binverse = 1
			if not div_3:
				binverse *= pow_mod(9, totient_m - 1, b * M)
			if not div_11:
				binverse *= pow_mod(11, totient_m - 1, b * M)
			if not div_101:
				binverse *= pow_mod(101, totient_m - 1, b * M)
		ten_power *= binverse
		answer = A * ten_power % M
		print(answer)


import sys

def rdigit_gen(n):
	if n == 0:
		yield 0
	while n:
		yield (n % 10)
		n //= 10

def solve(a, n, m):
	l = len(tuple(rdigit_gen(a)))

	def calc(n):
		if n == 1:
			return a % m
		if n % 2 == 0:
			k = n // 2
			u = calc(k)
			v = pow(10, l * k, m)
			return (u * v % m + u) % m
		k = n - 1
		u = calc(k)
		v = pow(10, l, m)
		return (u * v % m + a) % m
	return calc(n)
t = int(input())
for _ in range(t):
	(a, n, m) = map(int, input().split())
	print(solve(a, n, m))


import sys
import math

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


def cal(l, r, m):
	if l == 1:
		return 1
	if l & 1:
		return (pow(r, l - 1, m) + cal(l - 1, r, m)) % m
	return (1 + pow(r, l // 2, m)) * cal(l // 2, r, m) % m
for _ in range(int(input())):
	(a, n, m) = list(map(int, input().split()))
	print(a * cal(n, 10 ** len(str(a)), m) % m)


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


def matrixmul(p, q):
	z = [[], [0, 1]]
	z[0].append((p[0][0] * q[0][0] + p[0][1] * q[1][0]) % m)
	z[0].append((p[0][0] * q[0][1] + p[0][1] * q[1][1]) % m)
	return z

def matrixpow(q):
	x = 10 ** len(str(a)) % m
	c = [[x, 1], [0, 1]]
	b = [[1, 0], [0, 1]]
	while q > 0:
		if q % 2:
			b = matrixmul(b, c)
		c = matrixmul(c, c)
		q = q // 2
	return b
t = int(input())
for _ in range(t):
	(a, n, m) = map(int, input().split())
	if n == 1:
		ans = a % m
	else:
		b = matrixpow(n)
		ans = b[0][1] * a % m
	print(ans)


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def eugene(line):
	for i in range(int(next(line))):
		(a, n, m) = map(int, next(line).split())
		res = []
		(tmp, p, r) = (0, len(str(a)), a)
		while n:
			if n & 1:
				tmp = (tmp * pow(10, p, m) + r) % m
			(p, r) = (p << 1, (r * pow(10, p, m) + r) % m)
			n >>= 1
		res.append(tmp)
		print('\n'.join(map(str, res)))
eugene(sys.stdin)


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


for t in range(int(input())):
	(a, n, m) = map(int, input().split())
	d = 1
	if a > 9:
		if a < 100:
			d = 2
		elif a < 1000:
			d = 3
		else:
			d = 4
	m *= 10 ** d - 1
	ans = (pow(10, n * d, m) - 1) * (a % m) % m
	print(ans // (10 ** d - 1))


def rec(l, n, m):
	if n == 0:
		return 0
	if n == 1:
		return 10 ** (l - 1) % m
	h = rec(l, n // 2, m)
	if n & 1:
		return (h * pow(10, l + l * (n // 2), m) % m + h * 10 ** l % m + 10 ** (l - 1) % m) % m
	return (h * pow(10, l * (n // 2), m) % m + h) % m
for _ in range(int(input())):
	(a, n, m) = map(int, input().split())
	print(a * (rec(len(str(a)), n - 1, m) * 10 + 1) % m)


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


def solve(a, n, m):
	return (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, k, m) = map(int, input().split())
	print(solve(a, k, m))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


def solve(a, n, m):
	a = a % m
	pow10 = 10 ** len(str(a)) % m
	answer = 0
	while n:
		if n & 1:
			answer = (answer * pow10 % m + a) % m
		a = (a * pow10 % m + a) % m
		pow10 = pow10 * pow10 % m
		n >>= 1
	return answer
t = int(input())
for _4 in range(0, t):
	arr = list(map(int, input().split()))
	a = arr[0]
	b = arr[1]
	m = arr[2]
	ans = solve(a, b, m)
	print(ans)


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))


import sys

def power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (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 + power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + 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))