#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define LL unsigned long long
LL solve(LL a,LL b,LL mod){
    int s1[50],s2[50],s3[50],s1l = 0,s2l = 0,s3l = 0;
    LL ans = 0;
    while(a){
        s1[s1l++] = a%10;
        a/=10;
    }
    while(b){
        s2[s2l++] = b%10;
        b/=10;
    }
    memset(s3,0,sizeof(s3));
    int n = s1l+s2l,res = 0;
    for(int i = 0;i<s1l;i++){
        for(int j = 0;j<s2l;j++){
            s3[i+j]+=s1[i]*s2[j];
        }
    }
    for(int i = 0;i<=n;i++){
        if(s3[i]>=10){
            s3[i+1]+=s3[i]/10;
            s3[i]%=10;
        }
    }
    res = 0;
    for(int i = n+1;i>=0;i--){
        int t=(s3[i]+res*10)/2;
        res = s3[i]%2;
        s3[i] = t;
    }
    LL bit = 1;
    for(int i = 0;i<=n+1;i++){
        ans = (ans + s3[i]*bit%mod)%mod;
        bit=(bit*2)%mod*5%mod;
    }
    return ans;
}
int main()
{
    int t;
    ///freopen("in.txt","r",stdin);
    LL q,p;
    scanf("%d",&t);
    while(t--){
        cin >> q >> p;
        if(q<3){
            printf("0\n");
            continue;
        }
        LL ans = solve(q-2,q-1,p);
        cout << ans << endl;
    }
    return 0;
}