#include<cstdio>
#include<iostream>
using namespace std;
long long t,n,codeforces;
bool kj[77]={};
long long slove(long long a,long long b)
{
    long long te=a;
    for(int i=0;i<b;i++)
        te=te*2%codeforces;
    return te;
}
int main()
{
    //freopen("1","r",stdin);
    cin>>t;
    for(int ii=1;ii<=t;ii++)
    {
        cin>>n>>codeforces;
        long long n1=n-1,n2=n-2;
        if(n1%2==0)n1/=2;
        else n2/=2;
        long long temp=0;
        for(int i=0;i<=61;i++)
            if(n2&(1LL<<i))
                temp=(temp+slove(n1,i))%codeforces;
        cout<<temp<<endl;
    }
    return 0;
}