#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
unsigned long long mod_mul (unsigned long long x,unsigned  long long y,unsigned  long long p)        //(x*y)%p
{
    unsigned long long s = 0 ;
    while (y > 0) {
        if (y & 1) {
            s += x ;
            while (s >= p) s -= p ; 
        }
        x <<= 1 ; 
        while (x >= p) x -= p ;
        y >>= 1 ;
    } return s ;
}
int main()
{
    unsigned long long p,q,ans;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cin>>q>>p;
q -= 2 ;
ans = ((q % p) + mod_mul (q, q, p)) / 2 ;
ans%=p;

        cout<<ans<<endl;
    }
    return 0;
}