#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
long long q,MOD,a,b,ans,T;

ll find(ll a,ll n)
{
    if (!n) return 0;
    ll ans=find(a,n/2);
    ans=2*ans%MOD;
    if (n&1) (ans+=a)%MOD;
    return ans;
}

int main()
{
    cin>>T;
    while (T--)
    {
        cin>>q>>MOD;
        if (q==2)
        {
            cout<<0<<endl; continue;
        }
        a=(q-1)/2%MOD; b=q%MOD;
        ans=find(a,b);
        ans=(ans-(q-1)%MOD+MOD)%MOD;
        cout<<ans<<endl;
    }
}