#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define inf 1000000000
#define NN 101
#define esp 1e-8
#define LL long long
#define rep(i,s,t) for (register int i=s;i<=t;i++)
#define red(i,t,s) for (register int i=t;i>=s;i--)
#define vtson(k,x) for(register int k=o[x];k;k=nex[k])
using namespace std;
LL n,m,aa,bb,cc,mo,p;
inline LL read()
{
    LL t=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')f=(ch=='-')?-1:f,ch=getchar();
    while(ch<='9'&&ch>='0')t=t*10+ch-'0',ch=getchar();
    return t*f;
}

LL mul(LL a,LL k)
{
    LL res=0;
    for(;k;k>>=1,a=(a+a)%mo)
        if(k&1)res=(res+a)%mo;
    return res;
}

void work()
{
    scanf("%I64d%I64d",&n,&mo);
    LL ans,tmp,t1,t2;
    t1=n-1,t2=n-2;
    if(t1&1)t2>>=1;
    else t1>>=1;
    ans=mul(t1,t2);
//    ans=(ans-(n-1)/2)%mo+mo;
//    ans%=mo;
    printf("%I64d\n",ans);
}

int main()
{
//    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    int T=read();
    rep(i,1,T)
        work();
    return 0;
}