#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<cassert>
#define LL long long
#define LD double
#define inf 10000000000000000ll
using namespace std;


LL times(LL a,LL x,LL mo)
{
    /*LL tmp=(x*y-(LL)((LD)x/mo*y+1.0e-8)*mo);
    if (tmp<0) tmp+=mo;
    return tmp;*/
    long long ans=0;
    for (;x!=0;x>>=1)
    {
        if ((x&1)==1) ans=(ans+a)%mo;
        a=(a+a)%mo;
    }
    return ans;
}


int main()
{
    int t;scanf("%d",&t);
    while (t--)
    {
        long long n,mo;
        scanf("%I64d%I64d",&n,&mo);
        if (n<=2) {printf("0\n");continue;}
        long long d1=n-2,d2=n-1;
        if (d1%2==0) d1/=2;else d2/=2;
        printf("%I64d\n",times(d1,d2,mo));
    }
}