/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=100000,INF=0x3f3f3f3f;
int T;
typedef long long LL;
LL q,P;
LL mul(LL a,LL b){
    LL ans=0;
    while(b){
        if(b&1)ans=(ans+a)%P;
        a=(a+a)%P;
        b>>=1;
    }
    return ans;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%I64d",&q,&P);
        if(q==1||q==2){puts("0");continue;}
        else printf("%I64d\n",mul((q-1)/2,(q-2))%P);
    }
    return 0;
}