#include <fstream>
#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

long long count(int n, int p)
{
    n--;
    assert (n <= 100000000);
    vector<int> v(n + 1);
    v[0] = 0;
    for (int h = 0; ; h++)
    {
        for (int i = (1 << h); i < (1 << (h + 1)); i++)
        {
            v[i] = v[i - (1 << h)] + 1;
            if (i >= n)
                return v[n] % p;
        }
    }
}

int main()
{
    ifstream in("hat.in");
    ofstream out("hat.out");
    size_t n;
    in >> n;
    for (size_t i = 0; i < n; i++)
    {
        long long n, p;
        in >> n >> p;
        out << count(n, p) << "\n";
    }
}
