#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define ll long long
#define int128 __int128
#define ull unsigned long long
#define endl "\n"
#define pi acos(-1)
#define pii pair<int, int>
const double eps = 1e-6;
const int N = 1e6 + 10, M = 1010, INF = 0x3f3f3f3f;
const int mod = 998244353;

void solve()
{
    int p, m;
    cin >> p >> m;
    int ans = 0;
    int la = 0;
    if (m <= 100)
    {
        for (int g = 0; g <= m; g++)
        {
            if (((g ^ (p - 1)) % p + p) % p == 1)
            {
                int k = (g ^ (p - 1)) / p;
                // cout << g << " " << k << endl;
                ans++;
            }
        }
        cout<<ans<<endl;
        return ;
    }
    if(p==2)
    {
        cout<<m/2+1<<endl;
        return ;
    }
    int sum = ((m ^ (p - 1)) - 1) / p;
    int t = sum;
    for (int k = t + 1; k <= t + 10; k++)
    {
        if (((k * p + 1) ^ (p - 1)) <= m)
        {
            sum++;
        }
    }

    for (int k = t; k >= t - 10 && k > 0; k--)
    {
        if (((k * p + 1) ^ (p - 1)) > m)
        {
            sum--;
        }
    }
    cout <<  sum + 1 << endl;
}
signed main()
{
    ios;
    int T = 1;
    cin >> T;
    // cout << fixed << setprecision(8);
    for (int i = 1; i <= T; i++)
    {
        // cout << "Case " << i << ": ";
        solve();
    }

    return 0;
}