#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)
    

#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;
    }
}