#include<cstdio>
#include<iostream>
using namespace std;

typedef long long LL;

LL mul(LL a,LL b,LL mod){
    if(!b) return 0;
    if(b==1) return a%mod;
    LL ans=mul(a,b/2,mod);
    ans=ans*2ll%mod;
    if(b&1) (ans+=a)%=mod;
    return ans;
}
 
void work(){
    LL q,p;
    cin>>q>>p;
    LL ans=(q-1)/2ll;
    ans=mul(ans,q-2,p);
    cout<<ans%p<<endl;
}

int main(){
    int kase;
    cin>>kase;
    while(kase--) work();
    return 0;
}