import time
import math
import sys
def sums(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r
def f(n):
    r=0
    s1=0
    while n:
        r, n =  n % 10, n // 10
        s1=s1+math.factorial(int(r))
    return s1

def sf(n):
    return sums(f(n))

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

def sg(i):
    return sums(g(i))

def ssg(n):
    s=0
    for i in range(1,n+1):
        s=s+sg(i)
    return s

q=int(sys.stdin.readline())
out=[]
for i in range(q):
    n1,m1=(sys.stdin.readline()).split()
    n=int(n1)
    m=int(m1)
    v=ssg(n)
    out.append(v%m)
for i in out:
    sys.stdout.write(i)