#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define endl '\n'
using i128 = __int128;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const i64 inf = 2e18;
//-------------------------------------------
void solve()
{
    int P, m;
    cin >> P >> m;
    int mb = 33 - __builtin_clz(P - 1);
    int mm = (m >> mb) << mb;
    int ans = max((mm - 2) / P + 1, 0LL);
    int num = max(((mm - 2) / P), -1LL) * P + 1;
    num += P;
    while ((num >> mb) <= (mm >> mb))
    {
        if ((num ^ (P - 1)) <= m)
        {
            ans++;
        }
        num += P;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
        solve();
    return 0;
}