#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#define mem(x,y) memset(x,y,sizeof(x))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
#define bug puts("===========");
const double pi=(acos(-1.0));
const double eps=1e-8;
const ll INF=1e18+10;
const ll inf=1e14;
const int maxn=1000+10;
//const int mod=100000007;
/*===============================*/

ll mult_mod(ll a, ll b, ll c) {
    a %= c;
    b %= c;
    ll ret = 0;
    while(b) {
        if(b & 1) {
            ret += a;
            ret %= c;
        }
        a <<= 1;
        if(a >= c)a %= c;
        b >>= 1;
    }
    return ret;
}
ll q,mod,sum;
int main()
{
    int T_T,n;
    scanf("%d",&T_T);
    while(T_T--){
        scanf("%I64d%I64d",&q,&mod);
        if(q==2) {
            puts("0");
            continue;
        }
        q--;
        if(q%2==0) sum=mult_mod(q/2,q-1,mod);
        else sum=mult_mod(q,(q-1)/2,mod);
        printf("%I64d\n",sum);
    }
    return 0;
}