#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

ll mul(ll a, ll b, ll m) {
    ll r = 0, t = a;
    while( b ) {
        if( b & 1 )
            r = ( r + t ) % m;
        t = ( t + t ) % m;
        b >>= 1;
    }
    return r;
    
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        ll Q, P;
        cin >> Q >> P;
        ll z = 0;
        if( Q % 2 == 0 )
            z = mul((Q-3+P)%P, Q/2, P);
        else
            z = mul(((Q-3)/2 + P) % P, Q, P);
        z = (z + 1) % P;
        cout << z << endl;
    }
    return 0;
}