#include<iostream>
#include<cstring>
#include<cstdio>


using namespace std;

long long P,q,a,b,ans;
int T;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%lld%lld",&q,&P);
        b=q;
        a=q+1;
        if (a&1) b/=2;
        else a/=2;
        ans=0;
        while (b){
            if (b&1) ans=(ans + a)%P;
            b>>=1;
            a=(a+a)%P;
        }
        ans=(ans-q-q+1)%P;
        if (ans<0) ans+=P;
        printf("%lld\n",ans);
    }
    return 0;
}