#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define rpt(i,l,r) for(i=l;i<=r;i++)
#define rpd(i,r,l) for(i=r;i>=l;i--)
#define N 100005
using namespace std;
int T;
long long a,p;
long long solve(long long x,long long y){
    if(x==0) return 0;
    long long temp=solve(x>>1,y);
    (temp*=2)%=p;
    if(x&1) (temp+=y)%=p;
    return temp;
}
int main(){
    scanf("%d",&T);
    while(T--){
        cin>>a>>p;
        if(a%2==0) cout<<solve((a-2)/2,a-1)<<endl;
        else cout<<solve(a-2,(a-1)/2)<<endl;
        
    }
}