#include <cstdio>
#include <queue>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define LL long long
#define pii pair <int, int>
#define piii pair <pii, int>
#define xx first
#define yy second
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l, m
#define rson rs, m + 1, r
#define psi pair <string, int>
using namespace std;

const int N = 100500;

int main () {
//    freopen ("in.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        LL q, p;
        cin >> q >> p;
        if (q == 2) {
            cout << 0 << endl;
            continue;
        }
        q -= 2;
        LL a = q;
        LL b = q + 1;
        if (a % 2 == 0) a /= 2;
        else b /= 2;
        a %= p;
        b %= p;
        LL res = 0;
        while (b) {
            if (b & 1) (res += a) %= p;
            (a += a) %= p;
            b >>= 1;
        }
        cout << res << endl;
    }
}