#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll __int64
#define inf 2000000001
int scan()
{
    int res = 0 , ch ;
    while( !( ( ch = getchar() ) >= ‘0‘ && ch <= ‘9‘ ) )
    {
        if( ch == EOF )  return 1 << 30 ;
    }
    res = ch - ‘0‘ ;
    while( ( ch = getchar() ) >= ‘0‘ && ch <= ‘9‘ )
        res = res * 10 + ( ch - ‘0‘ ) ;
    return res ;
}
ll eluosimul(ll x,ll y,ll mod)
{
    ll sum=0;
    while(x)
    {
        if(x&1)
        {
            sum+=y;
            sum%=mod;
        }
        x>>=1;
        y*=2;
        y%=mod;
    }
    return sum;
}
int main()
{
    ll x,y,z,i,t,m,q;
    scanf("%I64d",&x);
    while(x--)
    {
        ll ans;
        scanf("%I64d%I64d",&q,&m);
        if(q%2)
        ans=eluosimul(q-2,(q-1)/2,m);
        else
        ans=eluosimul(q-1,(q-2)/2,m);
        printf("%I64d\n",ans);
    }
    return 0;
}

import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        int x;
        x=cin.nextInt();
        while(x!=0)
        {
            x--;
            BigInteger c=new BigInteger("2");
            BigInteger e=new BigInteger("1");
            BigInteger a=cin.nextBigInteger();
            BigInteger d=a.subtract(c);
            BigInteger f=a.subtract(e);
            BigInteger b=cin.nextBigInteger();
            BigInteger ans=f.multiply(d);
            ans=ans.divide(c);
            System.out.println(ans.remainder(b));
        }
    }
}