#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;

void solve(){
    ll p, m;
    cin >> p >> m;
    ll res = m / p;
    for(ll k = m / p ; k < m / p + 1000000; k ++) {
        ll t = k * p + 1;
        if((t ^ (p - 1)) <= m) {
            res ++;
        }
    }
    cout << res << '\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}