#include<iostream>
using namespace std;
typedef long long LL;
LL mul(LL u,LL v,LL p){
    LL d=0;
    for(;v;v>>=1){
        if(v&1)
            d=(d+u)%p;
        u=(u+u)%p;
    }
    return d;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        LL q,p;
        cin>>q>>p;
        if(q<3)
            cout<<0<<endl;
        else{
            LL u=q-2,v=q-1;
            if(u%2==0)
                u/=2;
            else
                v/=2;
            cout<<mul(u,v,p)<<endl;
        }
    }
}