#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#include<algorithm>
#include<set>
#include<vector> 
using namespace std;
typedef long long ll;
ll cal(ll a,ll b,ll p)
{
    ll sum=0;
    while(b)
    {
        if(b&1)
            sum+=a,sum%=p;
        a*=2,a%=p;
        b/=2;
    }
    return sum;
}
int main()
{ 
    int t;
    ll q,p,sum;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        scanf("%I64d %I64d",&q,&p);
        printf("%I64d\n",cal(q-1,q-2,2*p)/2);
    }
    return 0;
}