#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cctype>
#include <cstring>
using namespace std;

typedef long long LL;
LL Mul(LL a,LL b,LL p){
    LL ans=0;
    for(;b;b>>=1,a=(a<<1)%p)
        if(b&1) (ans+=a)%=p;
    return ans;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        LL q,p;
        cin>>q>>p;
        if(q&1) cout<<Mul(q-1>>1,q-2,p)<<endl;
        else cout<<Mul(q-2>>1,q-1,p)<<endl;
    }
    return 0;
}