#include <fstream>

using namespace std;

int main()
{
    ifstream in("hat.in");
    ofstream out("hat.out");
    int t;
    in >> t;
    for (int i = 0; i < t; i++)
    {
        long long n, p;
        in >> n >> p;
        n--;
        int ans = 0;
        while (n != 0)
        {
            n &= n - 1;
            ans++;
        }
        out << ans % p << "\n";
    }
}
