After dating for a long time, Akhil is finally going to propose to his girlfriend. She is very strong in mathematics, and will accept his proposal, if and only if Akhil solves a problem given by her. The problem is given below. Help Akhil solve it.

Akhil is given two numbers N and M, and he has to tell her the remainder when $111\cdots(\text{N times})$ is divided by $\mbox{M}$.  

Input Format 

The first line contains an integer ${T}$ i.e. the number of test cases. 

Each of the next ${T}$ lines contain two space separated integers, $N$ and $\mbox{M}$.  

Output Format 

${T}$ lines each containing ouptut for the corresponding test case. 

Constraints 

$1\leq T\leq10001$ 

$1\leq N\leq10^{16}$ 

$2\leq M\leq10^{9}$  

Sample Input 00  

3
3 3
4 7
5 18

Sample Output 00  

0
5   
5

Explanation 

111 % 3  = 0 

  1111 % 7 = 5 

  11111%18 = 5

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
T = int(input())
for tt in range(T):
	(N, M) = [int(x) for x in input().split()]
	ans = pow(10, N, 9 * M)
	ans = (ans - 1) // 9
	print(ans)


def bin(x, n, mod):
	y = 1
	while n > 0:
		if n & 1:
			y = y * x % mod
		x = x * x % mod
		n >>= 1
	return y
t = int(input())
for i in range(t):
	data = input().split(' ')
	n = int(data[0])
	m = int(data[1])
	ans = bin(10, n, 9 * m) // 9
	print(ans)


t = int(input())
for _ in range(t):
	(n, mod) = map(int, input().split())
	x = pow(10, n, mod * 9) - 1
	if x < 0:
		x += mod * 9
	print(x // 9)


T = int(input())

def pow(n, M):
	if n == 0:
		return 1
	half = pow(n // 2, M)
	if n % 2 == 0:
		return half * half % M
	else:
		return half * half * 10 % M
for t in range(T):
	(N, M) = map(int, input().split())
	M *= 9
	ans = pow(N, M) - 1
	assert ans % 9 == 0
	print(ans // 9)


t = int(input())
for _ in range(t):
	ID = input().split()
	n = int(ID[0])
	m = int(ID[1])
	r = 0
	d = 10
	e = 1
	while n > 0:
		if n % 2 == 1:
			r = (r * d + e) % m
		n //= 2
		e = (e * d + e) % m
		d = d * d % m
	print(r)


def sol(n, m):
	if n == 0:
		return (0, 1)
	h = sol(n >> 1, m)
	h = (h[0] * (1 + h[1]) % m, h[1] * h[1] % m)
	if n & 1:
		h = ((h[0] * 10 + 1) % m, h[1] * 10 % m)
	return h
for ti in range(int(input())):
	(n, m) = map(int, input().split())
	print(sol(n, m)[0])


def solve(N, M):
	if N == 1:
		return 1
	part1 = N // 2
	part2 = N - part1
	subRes1 = solve(part1, M)
	subRes2 = subRes1
	if part1 != part2:
		subRes2 = (subRes1 * 10 + 1) % M
	return (subRes1 * pow(10, part2, M) % M + subRes2) % M
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	print(solve(N, M))


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

def solve():
	(n, m) = [int(x) for x in input().split()]
	print(fast(10, n - 1, m))
t = int(input())
for i in range(t):
	solve()


def ans(N, M):
	ones_2p = 1
	ones_all = 0
	tens_2p = 10
	tens_all = 1
	while N:
		if N % 2 == 1:
			ones_all = (ones_all + ones_2p * tens_all) % M
			tens_all = tens_all * tens_2p % M
		ones_2p = (ones_2p + ones_2p * tens_2p) % M
		tens_2p = tens_2p * tens_2p % M
		N //= 2
	return ones_all
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	print(ans(N, M))


from functools import lru_cache

def solve_line(line_no, line):
	(num_digits, modulo) = list(map(int, line.split()))

	@lru_cache(maxsize=None)
	def solve1(num_digits):
		if num_digits < 2:
			return num_digits
		n = num_digits // 2
		return (solve1(n) * solve10(num_digits - n + 1) + solve1(num_digits - n)) % modulo

	@lru_cache(maxsize=None)
	def solve10(num_digits):
		if num_digits < 2:
			return num_digits
		if num_digits == 2:
			return 10 % modulo
		n = (num_digits + 1) // 2
		return solve10(n) * solve10(num_digits + 1 - n) % modulo
	return solve1(num_digits)

def solve(inputs):
	next(inputs)
	for (line_no, line) in enumerate(inputs, start=1):
		yield solve_line(line_no, line)

def interact(fun):

	def inputs():
		try:
			while True:
				yield input()
		except EOFError:
			pass
	outputs = fun(inputs())
	if outputs is not None:
		for line in outputs:
			print('' if line is None else line)
interact(solve)


def tenPow(p, m):
	t = 10 % m
	ans = 1
	while p:
		if p & 1:
			ans = ans * t % m
		t = t * t % m
		p >>= 1
	return ans

def func(k, m):
	if k == 1:
		return 1
	else:
		t = func(k // 2, m)
		if k & 1:
			return ((t * 10 + 1) * tenPow(k // 2, m) + t) % m
		else:
			return (t * tenPow(k // 2, m) + t) % m
for i in range(int(input())):
	(N, M) = [int(i) for i in input().split()]
	print(func(N, M))


import math
t = input()
l = []
for i in range(0, int(t)):
	m = input()
	a = m.split()
	a = [int(j) for j in a]
	l.append(a)

def f(x, m):
	if x == 1:
		return 1
	elif x % 2 == 0:
		d = f(x // 2, m)
		return d * (pow(10, x // 2, m) + 1)
	else:
		d = f(x // 2, m)
		return (d * 10 + 1) * pow(10, x // 2, m) + d
for i in l:
	print(f(i[0], i[1]) % i[1])


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print((pow(10, N, 9 * M) - 1) % (9 * M) // 9)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print((pow(10, N, 9 * M) - 1) % (9 * M) // 9)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print((pow(10, N, 9 * M) - 1) % (9 * M) // 9)


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


import sys

def pow_mod(x, n, m):
	if not n:
		return 1 % m
	if n % 2:
		return x % m * pow_mod(x, n - 1, m) % m
	std = pow_mod(x, n / 2, m)
	return std * std % m

def main(n, m):
	assert m > 0
	tmp = (pow_mod(10, n, m * 9) - 1 % (m * 9)) % (m * 9)
	return tmp / 9
problems = []
for (i, _) in enumerate(sys.stdin):
	ab = _.split()
	if not i:
		number = int(ab[0])
	else:
		a = int(ab[0])
		b = int(ab[1])
		problems.append([a, b])
	if i == number:
		break
for (a, b) in problems:
	print(int(main(a, b)))


def egcd(a0, a1):
	(x0, x1, y0, y1, b, n) = (1, 0, 0, 1, a0, a1)
	while n != 0:
		(q, b, n) = (b // n, n, b % n)
		(x0, x1) = (x1, x0 - q * x1)
		(y0, y1) = (y1, y0 - q * y1)
	return (b, x0, y0)

def modinv(n, p):
	return egcd(n, p)[1] % p
T = int(input().strip())
for _ in range(T):
	(N, M) = list(map(int, input().strip().split()))
	if M % 3 == 0:
		print((pow(10, N, M * 9) - 1) // 9)
	else:
		print((pow(10, N, M) - 1) * modinv(9, M) % M)


def getGF(n, m):
	powersOfTen = [10]
	repeatedOnes = [1]
	exp = 2
	index = 1
	while exp <= n:
		repeatedOnes.append((1 + powersOfTen[index - 1]) * repeatedOnes[index - 1] % m)
		powersOfTen.append(powersOfTen[index - 1] ** 2 % m)
		exp *= 2
		index += 1
	total = 0
	exp = 1
	index = 0
	while exp <= n:
		if n & exp:
			total = (powersOfTen[index] * total + repeatedOnes[index]) % m
		exp *= 2
		index += 1
	return total
line = input()
ctests = int(line)
for itest in range(ctests):
	line = input()
	tokens = line.split()
	n = int(tokens[0])
	m = int(tokens[1])
	print(getGF(n, m))


T = int(input())
a = []
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	a.append((pow(10, N, 9 * M) - 1) % (9 * M) // 9)
for i in range(T):
	print(a[i])


dict = {}

def get(x, y):
	if x == 0:
		return 0
	if x == 1:
		return 1
	if (x, y) in dict:
		return dict[x, y]
	a = x // 2
	b = x - a
	dict[x, y] = (get(a, y) * pow(10, b, y) + get(b, y)) % y
	return dict[x, y]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(get(n, m))


T = int(input().strip())
for _ in range(T):
	(N, M) = input().strip().split()
	(N, M) = (int(N), int(M))
	print((pow(10, N, 9 * M) - 1) // 9 % M)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	print((pow(10, n, 9 * m) - 1) % (9 * m) // 9)


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

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = map(int, input().split())
		print(geo_sum_mod(10, N - 1, M))
main()


T = int(input())
for tt in range(T):
	(N, M) = [int(x) for x in input().split()]
	ans = pow(10, N, 9 * M)
	ans = ans // 9
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	m *= 9
	ret = 1
	power = 10
	while n != 0:
		if n & 1 != 0:
			ret = ret * power % m
		n >>= 1
		power = power ** 2 % m
	print((ret - 1) // 9)


T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	a = 1
	b = 10
	c = 0
	d = 1
	while N:
		if N & 1:
			c = (c + d * a) % M
			d = d * b % M
		a = (a + a * b) % M
		b = b * b % M
		N >>= 1
	print(c)


def solve(x, y):
	if x == 0:
		return 0
	if x % 2 == 0:
		return solve(x // 2, y) * (1 + pow(10, x // 2, y)) % y
	else:
		return (solve(x - 1, y) + pow(10, x - 1, y)) % y
for i in range(int(input())):
	l = list(map(int, input().split()))
	print(solve(l[0], l[1]))


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


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	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

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 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 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 euler_totient_with_factors(n, factors):
	for ar_elet in factors:
		n //= ar_elet[0]
		n *= ar_elet[0] - 1
	return n

def gcd_matrix_coefficients(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][0], M[1][1])
		else:
			return (M[0][0], M[0][1])
	elif a != 0 and b != 0:
		return gcd_matrix(abs(a), abs(b))
	else:
		return (0, 0)

def chinese_remainder_theorem(x_list, mod_list):
	current_mod = mod_list[0]
	current_x = x_list[0]
	for i in range(1, len(x_list)):
		(a, b) = gcd_matrix_coefficients(current_mod, mod_list[i])
		current_x = current_x * b * mod_list[i] + x_list[i] * a * current_mod
		current_mod *= mod_list[i]
	return current_x % current_mod

def compute_eleventy(N, M, PL):
	factors_of_M = factor(M, PL)
	num = pow_mod(10, N, 9 * M) - 1
	if M % 9 == 0 and N % 9 == 0:
		if num % 9 == 0:
			num //= 9
			den = 1
		elif num % 3 == 0:
			num //= 3
			den = 1
		else:
			num //= 1
			den = 1
	elif M % 9 == 0 and N % 3 == 0:
		if num % 9 == 0:
			num //= 9
			den = 1
		elif num % 3 == 0:
			num //= 3
			den = pow_mod(3, euler_totient_with_factors(M, factors_of_M) - 1, 9 * M)
		else:
			num //= 1
			den = 1
	elif M % 3 == 0 and N % 3 == 0:
		num //= 3
		den = pow_mod(3, euler_totient_with_factors(M, factors_of_M) - 1, 3 * M)
	elif M % 3 == 0 and N % 3 != 0:
		if num % 9 == 0:
			num //= 9
			den = 1
		elif num % 3 == 0:
			num //= 3
			den = pow_mod(3, euler_totient_with_factors(M, factors_of_M) - 1, 3 * M)
		else:
			num //= 1
			den = 1
	else:
		den = pow_mod(9, euler_totient_with_factors(M, factors_of_M) - 1, 9 * M)
	ans = num * den % M
	return ans % M
PL = prime_list(100000)
T = int(input())
for _ in range(T):
	(N, M) = [int(a) for a in input().split()]
	print(compute_eleventy(N, M, PL))


import sys

def primes_gen(n):
	sieve = [True] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = False

def pf_gen(n, prms):
	if n < 2:
		return
	for p in prms:
		if p > n:
			return
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt > 0:
			yield (p, cnt)
	if n > 1:
		yield (n, 1)

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def is_coprime(n, m):
	return True

def mod_inv(n, m):
	return pow(n, m - 2, m)

def solve_incorrect(n, m):
	print('n=%d m=%d' % (n, m), file=sys.stderr)
	if is_coprime(n, m):
		u = (pow(10, n, m) - 1) % m
		u *= mod_inv(9, m)
		return u % m
	return None

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


def powmod(base, exp, mod):
	ans = 1
	a = base
	while exp > 0:
		if exp & 1 == 1:
			ans = ans * a % mod
		a = a * a % mod
		exp = exp >> 1
	return ans
t = int(input())
for x in range(t):
	ins = input().split(' ')
	n = int(ins[0])
	m = int(ins[1])
	p = (powmod(10, n, 9 * m) + 9 * m - 1) % (9 * m)
	ans = p // 9 % m
	print(ans)


import math
import itertools

def powerModulo2(a, b, mod):
	a %= mod
	if b == 1:
		return a
	temp = powerModulo2(a, int(b / 2), mod)
	if b % 2 == 0:
		return temp * temp % mod
	else:
		return a * (temp * temp) % mod % mod

def powerModulo(a, b, mod):
	a %= mod
	if b == 1:
		return a
	if b == 2:
		return a * a % mod
	if b == 3:
		return a * (a * a % mod) % mod
	temp = powerModulo(a, int(b / 3), mod)
	if b % 3 == 0:
		return temp * (temp * temp % mod) % mod
	elif b % 3 == 1:
		return a * (temp * (temp * temp % mod) % mod) % mod
	else:
		return a * a % mod * (temp * (temp * temp % mod) % mod) % mod
numCases = int(input())
for i in range(numCases):
	[n, m] = map(int, input().split())
	print(int((powerModulo(int(10), n, int(9) * m) - int(1)) / int(9)))


def main():
	for a in range(int(input())):
		(N, M) = [int(num) for num in input().split()]
		if N == 0:
			print(0)
		elif N == 1:
			print(1)
		elif N == 2:
			print(11 % M)
		elif N == 3:
			print(111 % M)
		else:
			power = pow(10, N, 9 * M)
			ans = (power - 1) // 9
			print(ans)
main()


def oneMod(n, m):
	if n <= 10:
		newNum = pow(10, n) // 9
		return newNum % m
	elif n % 2 == 0:
		x = oneMod(n // 2, m) % m
		return (pow(10, n // 2, m) * x + x) % m
	else:
		x = oneMod(n // 2, m) % m
		return (pow(10, n // 2 + 1, m) * x + x * 10 + 1) % m
testCases = int(input(''))
while testCases < 1 or testCases > 10001:
	testCases = int(input(''))
for x in range(testCases):
	nums = input('')
	(n, m) = nums.split(' ')
	(n, m) = (int(n), int(m))
	print(oneMod(n, m))


num_of_inputs = int(input())
num_of_ones = []
mod_nums = []
for i in range(num_of_inputs):
	to_parse = input()
	to_parse = to_parse.split(' ')
	num_of_ones.append(int(to_parse[0]))
	mod_nums.append(int(to_parse[1]))

def mod(x, y):
	return int((pow(10, x, 9 * y) - 1) / 9 % y)
from math import floor
for pos in range(num_of_inputs):
	print(mod(num_of_ones[pos], mod_nums[pos]))


def big_mod(n, m):
	if n == 1:
		return (1, 10 % m)
	(a, b) = big_mod(n // 2, m)
	y = b * b % m
	x = (a * b + a) % m
	if n % 2 == 1:
		y = y * 10 % m
		x = (x * 10 + 1) % m
	return (x, y)
cases = int(input())
for i in range(cases):
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	(res, _) = big_mod(n, m)
	print(res)


def big_mod(n, m):
	if n == 1:
		return (1, 10 % m)
	(a, b) = big_mod(n // 2, m)
	y = b * b % m
	x = (a * b + a) % m
	if n % 2 == 1:
		y = y * 10 % m
		x = (x * 10 + 1) % m
	return (x, y)
cases = int(input())
for i in range(cases):
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	(res, _) = big_mod(n, m)
	print(res)


def big_mod(n, m):
	if n == 1:
		return (1, 10 % m)
	(a, b) = big_mod(n // 2, m)
	y = b * b % m
	x = (a * b + a) % m
	if n % 2 == 1:
		y = y * 10 % m
		x = (x * 10 + 1) % m
	return (x, y)
cases = int(input())
for i in range(cases):
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	(res, _) = big_mod(n, m)
	print(res)


Num = int(input())
for n in range(Num):
	(N, M) = [int(x) for x in input().split()]
	ans = pow(10, N, 9 * M)
	ans = (ans - 1) // 9
	print(ans)


T = int(input())
for alpha in range(T):
	(n_value, m_mod) = map(int, input().split())
	i = pow(10, n_value, m_mod * 9) - 1
	if i < 0:
		i += m_mod * 9
	print(i // 9)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = pow(10, n, m * 9)
	print((p - 1) // 9)


def extendedGCD(a, b):
	(m00, m01, m10, m11) = (1, 0, 0, 1)
	while b != 0:
		k = a // b
		(m00, m01, m10, m11) = (m10, m11, m00 - k * m10, m01 - k * m11)
		(a, b) = (b, a - k * b)
	return (m00, m01, a)

def modinv(x, p):
	(a, b, g) = extendedGCD(x, p)
	return a

def powerMod(base, exponent, modulus):
	result = 1
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		base = base * base % modulus
		exponent //= 2
	return result

def RemainderFromMultipleOnes(n, m):
	return (powerMod(10, n, 9 * m) - 1) // 9
T = int(input())
for i in range(T):
	(N, M) = [int(x) for x in input().split()]
	print(RemainderFromMultipleOnes(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):
	c = [[10, 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):
	(n, m) = map(int, input().split())
	a = 1
	if n == 1:
		ans = 1
	else:
		b = matrixpow(n)
		ans = b[0][1] % m
	print(ans)


import os
import sys
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = pow(10, n, m * 9)
	print((p - 1) // 9)


import math
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	ans = pow(10, n, 9 * m)
	print((ans - 1) // 9)
	t = t - 1


import sys

def akhil(line):
	for i in range(int(next(line))):
		(n, m) = map(int, next(line).split())
		res = []
		(tmp, p, r) = (0, 1, 1)
		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)))
akhil(sys.stdin)


def f(n, m):
	if n == 0:
		return 0
	if n == 1:
		return 1
	if n == 2:
		return 11 % m
	t = f(n // 2, m) % m
	x = n // 2
	if n % 2:
		x += 1
		return (t * pow(10, x, m) + 10 * t + 1) % m
	return (t * pow(10, x, m) + t) % m
t = int(input())
for _ in range(t):
	e = input().split()
	n = int(e[0])
	m = int(e[1])
	ans = f(n, m)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = pow(10, n, m * 9)
	print((p - 1) // 9)


import os
import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, M) = list(map(int, sys.stdin.readline().split()))
	print((pow(10, N, 9 * M) - 1) % (9 * M) // 9)


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = pow(10, n, m * 9)
	print((p - 1) // 9)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = pow(10, n, m * 9)
	print((p - 1) // 9)


for i in range(int(input())):
	(b, c) = map(int, input().split(' '))
	ans = pow(10, b, 9 * c)
	ans = 1 * ((ans - 1) // 9)
	print(ans % c)