#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<algorithm>
#include<math.h>
#include<cmath>
using namespace std;
__int64 p,q;
__int64 mul(__int64 a,__int64 b,__int64 mod){
    __int64 n = 0;
    while(b){
        if(b&1)
          n = (n+a)%mod;
        a = (a*2)%mod;
        b /= 2;
    }
    return n;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%I64d%I64d",&q,&p);
       printf("%I64d\n",mul(q-1,q-2,2*p)/2);
       
    }
    return 0;
}