#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

int GetDigit(ull x)
{
    return log2(x) + 1;
}

ull Solve1(ull p, ull m)
{
    int d_up = GetDigit(m);
    ull k = 0, res = 0;
    while (GetDigit(k * p + 1) <= d_up)
    {
        if (((k * p + 1) ^ (p - 1)) <= m)
            res++;
        k++;
    }

    return res;
}

ull Solve2(ull p, ull m)
{
    int d_ps1 = GetDigit(p - 1);
    ull full = m & (-1ULL - (ull)(pow(2, d_ps1 + 1) - 1));

    ull res = full / p;
    if (full % p)
        res++;
    if (!full)
        res = 0;

    ull start = full / p * p + 1;
    while (start <= full)
        start += p;
    for (int i = 0; i <= 4; i++)
        if (((start + i * p) ^ (p - 1)) <= m)
            res++;

    return res;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ull p, m;
        cin >> p >> m;

        if (!m)
        {
            int ans = 0;
            if (p == 2)
                ans++;
            cout << ans << '\n';
        }
        else
        {
            if (GetDigit(p - 1) >= GetDigit(m))
                cout << Solve1(p, m) << '\n';
            else
                cout << Solve2(p, m) << '\n';
        }
    }

    return 0;
}