#include<cstdio>

typedef long long LL;

LL mul(LL x,LL y,LL p){
    LL ans=0;
    while(y){
        if(y&1)ans=(ans+x)%p;
        x=(x+x)%p; y>>=1;
    }
    return ans;
}

int main(){
    int _; scanf("%d",&_);
    while(_--){
        LL ans=0,n,p; scanf("%I64d%I64d",&n,&p);
        if(n<=2){
            printf("0\n");
            continue;
        }
        LL m=n+1;
        m-=2; n-=2;
        if(m&1)n>>=1;
        else m>>=1;
        printf("%I64d\n",mul(n%p,m%p,p));
    }
}