#include <cstdio>
#include <algorithm>

using namespace std;

int T;
long long q,mod;
long long xmul(long long x,long long y){
    if (x==0) return 0;
    if (x==1) return y;
    if (x % 2==0){
        long long kkk=xmul(x/2,y);
        return kkk*2 % mod;
    }
    else{
        long long kkk=xmul(x/2,y);
        return (kkk*2+y) % mod;
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%I64d",&q,&mod);
        if (q % 2==0) printf("%I64d",xmul(q-1,(q-2)/2));
        else printf("%I64d",xmul((q-1)/2,q-2));
        putchar(10);
    }
}