import sys
import math
import time
import timeit
from decimal import Decimal
def f(n):
    #return sum([int(i) * f(str(int(i) - 1)) if int(i) > 1 else 1 for i in n])
    return sum(math.factorial(int(i)) for i in n)
def sf(n):
    return sum(int(i) for i in str(f(n)))
def sg(n):
    dfg = DefindG(n)
    return sum(int(d) for d in str(dfg))
def ms(n):
    d_sg = {1: 1, 2: 2, 3: 5, 4: 6, 5: 7, 6: 3, 7: 4, 8: 5, 9: 6, 10: 7,
            11: 8, 12: 8, 13: 9, 14: 13, 15: 9, 16: 10, 17: 11, 18: 13,
            19: 14, 20: 15, 21: 16, 22: 17, 23: 18, 24: 13, 25: 14, 26: 15,
            27: 9, 28: 10, 29: 11, 30: 12, 31: 13, 32: 14, 33: 12, 34: 13,
            35: 14, 36: 15, 37: 19, 38: 28, 39: 24, 40: 25, 41: 37, 42: 31,
            43: 32, 44: 45, 45: 46, 46: 50, 47: 66, 48: 67, 49: 71, 50: 84,
            51: 89, 52: 90, 53: 114, 54: 118, 55: 134, 56: 154, 57: 158, 58: 193,
            59: 231, 60: 235, 61: 247, 62: 317, 63: 321, 64: 545, 65: 843, 66: 1052,
            67: 1339, 68: 1574, 69: 1846, 70: 2035, 71: 2294, 72: 2566, 73: 5035,
            74: 7578, 75: 9997, 76: 12529, 77: 15009, 78: 17415, 79: 19912, 80: 22416,
            81: 24933, 82: 49686, 83: 74498, 84: 99334, 85: 124135, 86: 148899,
            87: 173672, 88: 198536, 89: 223324, 90: 248145, 91: 496173, 92: 744212,
            93: 992162, 94: 1240190, 95: 1488229, 96: 1736179, 97: 1984255,
            98: 2232318, 99: 2480268, 100: 4960419, 101: 7440581, 102: 9920765,
            103: 12400916, 104: 14881015, 105: 17361186, 106: 19841385, 107: 22321571}
    #return sum(sg(i) for i in range(1, n + 1))
    return sum(d_sg[i] for i in range(1, n + 1))
def StartFrom(n):  # this function returns The first possible compilation group for (n)
    r = int()
    for nf in range(9, 0, -1):
        if n >= nf:
            r = int(n / nf)
            m = f"{r * str(nf)}"
            m = f"{(n - (sum(int(j) for j in m)))}{r * str(nf)}"
            return int(m)
def SumIntegers(n):
    return sum(int(i) for i in str(n))
def Findf(n):  # 389,999,999,999 EX SUM = 101 3000*F9 +1000*F8 +
    temp = n
    qum = ''  # fac 9
    fac = (1, 2, 6, 24, 120, 720, 5040, 40320, 362880)  # factorials from 1-9
    for i in range(1, 10):
        s = 0
        m = (10 - i)
        divf = int(n / fac[m - 1])
        if divf > 0:
            qum += divf * str(m)  # other choice F(m)
            n = int(n % fac[m - 1])
    return qum[::-1]  # , int(qum[::-1])
def fastsums(n, i, note):
    end = False
    lenthI = int(math.log10(i))  # len(str(i)) - 1
    lNum = int(str(i)[-1])
    if SumIntegers(i + 1) == n: # and '0' not in str(i + 9)
        i = i + 1
        note = int(math.log10(i))
        #print(i, 'DER', 9, note)
    elif SumIntegers(i + 9) == n: # and '0' not in str(i + 9)
        i = i + 9
        note = int(math.log10(i))
        #print(i, 'DER', 9, note)
    elif lNum > 1:
        checked = False
        for z in range(0, lenthI):
            surplus = int(f'{lNum}{z * "0"}{9 - lNum}')
            if SumIntegers(i + surplus) == n: # and '0' not in str(i + surplus)
                i = i + surplus
                note = int(str(surplus).count('0'))
                if note != 0 and lNum < 9:
                    note = note + 1
                if note == 0:
                    note = int(math.log10(i))
                #print(i, 'SUR', surplus, note)
                checked = True
                break
        if checked is False:
            for ez in range(9, int((lenthI + 3) * '9')):
                if SumIntegers(i + ez) == n: # '0' not in str(i + ez) and
                    i = i + ez
                    note = int(str(ez).count('0'))
                    lez = int(str(ez)[-1])
                    if note != 0 and lez < 9:
                        note = note + 1
                    if note == 0:
                        note = int(math.log10(ez))
                    #print(i, 'EZ', ez, note)
                    break
    elif lNum == 1 or lNum == 0:
        checked = False
        if lNum == 1 and i > 100:
            lNum2 = int(str(i)[:lenthI - 2:-1])
            strlNum2 = str(i)[:lenthI - 2:-1]
            for z in range(0, note):  # lenthI
                surplus = int(f'{lNum2}{z * "0"}{9 - int(strlNum2[1])}{9 - int(strlNum2[0])}')
                if SumIntegers(i + surplus) == n and surplus != 0:
                    i = i + surplus
                    note = int(str(surplus).count('0'))
                    checked = True
                    #print(i, 'NUM1', surplus, note)
                    break
        if checked is False or lNum == 0 :
            if str(i).count('1') != len(str(i)):
                for ez in range(9, int((lenthI + 3) * '9')):
                    if SumIntegers(i + ez) == n: #'0' not in str(i + ez) and
                        i = i + ez
                        note = int(str(ez).count('0'))
                        lez = int(str(ez)[-1])
                        if note != 0 and lez < 9:
                            note = note + 1
                        if note == 0:
                            note = int(math.log10(ez))
                        #print(i, 'EZ1', ez, note)
                        break
            else:
                end = True
    return i, note, end
def DefindG(n):
    if n == 1:return '1'
    if n == 2:return '2'
    if n == 3:return '5'
    #if n == 9:return '6'
    resultat = str()
    h = StartFrom(n)
    note = int(math.log10(h))
    rs = 0
    start_time = time.time()
    seconds = 5
    count = 0
    while True:
        count += 1
        current_time = time.time()
        elapsed_time = current_time - start_time
        q = Findf(h)
        #print(q,    h)
        countq = len(q)
        #print(countq)
        #counqq = ''.join(q.split('9'))
        #print(q ,2355679)
        if rs == 0:
            rs = len(q) + 999
        # print('\r', h, sf(q), end='', flush=True)
        if sf(q) == n and countq <= rs:
            if countq < rs:
                resultat = q
                rs = countq
            else:
                #tttsr = ''.join(resultat.split('9'))
                if int(q[:100]) < int(resultat[:100]):
                    resultat = q
                    rs = countq
        res, note, end = fastsums(n, h, note) #here is the problem 5 most returns 122 AND ITS LIMIT IS 50
        h = res
        if elapsed_time > seconds or end is True: #elapsed_time > seconds or
            break
        #print(resultat)
    return resultat    # int(math.log10(q)))



data = sys.stdin.read().splitlines()   # Use Ctrl d to stop the input 
for i in data:
    m = i.split()
    if len(m) > 1:
        print(ms(int(i.split()[0])) )
    else : pass
    
    

#include <iostream>
using namespace std;

int f (int num) {
    int fact = num;
    if (num == 0) {
        fact = 1;
    }
    else {
    for (int i = num-1; i>0; --i) {
        fact = fact * i;
    }
    }
    return fact;
}

int fn (int n) {
    int sum_f=0;
    string temp = to_string(n);
    for (int i = 0; i<temp.length(); ++i) {
        int conv_i = temp[i] - 48;
        sum_f += f(conv_i);
    }
    return sum_f;
}

int sfn (int num) {
    int sum_fn=0;
    int sum_f = fn(num);
    string temp = to_string(sum_f);
    for (int i = 0; i<temp.length(); ++i) {
        int conv_i = temp[i] - 48;
        sum_fn += conv_i;
    }
    return sum_fn;
}

int gi (int num) {
    int sum_fn;
    int i = 0;
    while (num != sum_fn) {
        ++i;
        sum_fn = sfn(i);
    }
    return i;
}

int sgi (int num) {
    int sum_gi=0;
    for (int i = 1; i<=num; ++i) {
        int temp = gi(i);
        if (temp < 10) {
            sum_gi += temp;
        }
        else {
            string s_temp = to_string(temp);
            for (int j = 0; j<s_temp.length(); ++j) {
                int conv_i = s_temp[j] - 48;
                sum_gi += conv_i;
            }
        }
    }
    return sum_gi;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int q, n, m;
    cin >> q;
    for (int i = 0; i<q; ++i) {
        cin >> n >> m;
        cout << sgi(n) << endl;
    }
}

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)