#include<iostream>
using namespace std;
typedef unsigned long long ull;
int main()
{
    ull p,q,T,base,ans,i,x,y;
    cin>>T;
    while(T--)
    {
        ans=0;
        cin>>q>>p;
        x=q-1,y=q-2;
        if(x%2==0)
            x/=2;
        else
            y/=2;
        for(i=base=1;i<64;i++,base<<=1,y=(y*2)%p)
        {
            if(x&base)
                ans=(ans+y)%p;
        }
        cout<<ans<<endl;
    }
    return 0;
}