#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define x first
#define y second
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
void solve()
{
    int p, m;
    cin >> p >> m;
    int k = m / p, ans = k;
    for (int i = k; i < k + 10; i++)
    {
        if (((i * p + 1) ^ (p - 1)) <= m) ans++;
    }
    // if ((1 ^ (p - 1)) <= m) ans++;
    cout << ans << endl;
}
signed main()
{
    // freopen("D:\\3022244240\\vscode\\txt\\in.txt", "r", stdin);
    // freopen("D:\\3022244240\\vscode\\txt\\out.txt", "w", stdout);
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}