#include <iostream>
using namespace std;
typedef long long LL;
LL mul(LL a, LL n, LL p){
LL r = 0;
// a%=p;n%=p; 加这句就过了，能解释下吗
while(n){
if(n&1) r+=a;
if(r>=p) r-=p;
n>>=1; a+=a;
if(a>=p) a-=p;
}
return r;
}
int main(){
// freopen("/Users/dna049/Desktop/AC/in","r",stdin);
// freopen("/Users/dna049/Desktop/AC/out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
LL n,q,x,y;
cin>>n>>q;
if(n&1){
x=(n-1)>>1;
y=(n-2);
}else{
x=n-1;
y=(n-2)>>1;
}
cout<<mul(x,y,q)<<endl;
}
return 0;
}
