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

typedef long long ll;

ll P;

ll mult(long long x, long long y)
{
    ll ans=0;
    while(x)
    {
    //printf("%I64d\n",x);
    //getchar();
    if(x&1)
        ans=(ans+y)%P;
        y=(y+y)%P;
    x>>=1;
    }
    return ans;
}

int main()
{
    ll q, x, y;
    int T;
    scanf("%d",&T);
    while(T--)
    {
    scanf("%lld%lld",&q,&P);
    if(q<3)
    {
        puts("0");
        continue;
    }
    if(q&1)
    {
        x = (q-3)/2;
        y = q;
    }
    else
        {
        x = q-3;
        y = q/2;
    }
    x=mult(x,y);
    x=(x+1)%P;
    printf("%I64d\n",x);
    }
    return 0;
}