#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
typedef pair<int, int> PII;
int a[N];
void solve()
{
    int p, m;
    cin >> p >> m;
    int loop = -1;

    // 确定循环节
    for (int i = 0; i <= 100; i++)
    {
        if (a[i] >= p)
        {
            loop = i;
            break;
        }
    }
    // vector<int> u;
    // for (int i = 1; i <= a[loop] + 1; i++)
    // {
    //     int w = (i - 1ll) * p + 1ll;
    //     int g = w ^ (p - 1ll);
    //     u.push_back(g);
    // }
    // sort(u.begin(), u.end());
    int first = 0;
    // 找第一个数
    for (int i = 0; i <= 100; i++)
    {
        int x = i ^ (p - 1ll);
        if (x % p == 1ll)
        {
            first = i;
            break;
        }
    }
    if (m < first)
    {
        cout << 0 << '\n';
        return;
    }
    int dx = p * a[loop];
    int ans = (m - first) / dx;
    int v = first + ans * dx;
    ans = ans * loop + 1ll;
    for (int i = v + 1; i <= m; i++)
    {
        if (((i ^ (p - 1ll)) % p) == 1ll)
            ans++;
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    a[0] = 1;
    for (int i = 1; i <= 2e5; i++)
        a[i] = a[i - 1] * 2ll;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}