#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        __int64 p,q,sign1,sign2;
        scanf("%I64d%I64d",&p,&q);
        if(p<=2) cout<<"0"<<endl;
        else
        {
            p=p%q;
            sign1=p-1;
            sign2=p-2;
            if(sign1%2==0) sign1=sign1/2;
            else sign2=sign2/2;
            __int64 i=0,flag;
            __int64 ans=0,gg;
            while(sign2)
            {
                flag=i;
                gg=((sign1%q)*(sign2%10))%q;
                while(flag--)
                {
                     gg=(gg*10)%q;
                }
                ans+=gg;
                ans=ans%q;
                sign2=sign2/10;
                i++;
            }
            cout<<ans%q<<endl;
        }
    }
    return 0;
}