#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
//#include <unordered_map>
using namespace std;
#define FOR(i, n, m) for(int i = n; i <= m; i++)
#define REP(i, n, m) for(int i = n; i >= m; i--)
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, int> PLI;

const int maxn = 200010;
const int maxm = 100010;

ll mul(ll a,ll k,ll mod){
    ll n = 0;
    while(k){
            if(k&1) n = (n+a)%mod;
            a = (a << 1) % mod;
            k >>= 1;
            }
        return n;
    }

int main(){
        int t;
        cin>>t;
        ll q, p;
        while(t--){
            cin>>q>>p;
            cout<<mul(q-1, q-2, p*2)/2<<endl;
           }
        return 0;
        }