//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 1e5 + 5;

ll n, m;

void MAIN() {
    cin >> n >> m;
    vector<pair<ll, ll>> li;
    ll now = 0, pn = 0, nn = n - 1;
    for (int i = 62; i >= 0; i--) {
        int v = ((m >> i) & 1);
        pn |= (nn & (1ll << i));
        if (v == 0) continue;
        ll r = (now | pn) + (1ll << i) - 2, l = max((now | pn) - 1, 0ll);
        if (l > r) {
            now |= 1ll << i;
            continue;
        }
        l = (l + n - 1) / n; r = r / n;
        if (l <= r) li.push_back({l, r});
        now |= 1ll << i;
    }
    now ^= pn;
    --now;
    if (now % n == 0) li.push_back({now / n, now / n});
    sort(li.begin(), li.end());
    //for (auto [x, y] : li) cout << x << ' ' << y << '\n';
    ll mxt = -1;
    ll ans = 0;
    for (auto [x, y] : li) {
        if (y > mxt) ans += y - max(mxt, x - 1), mxt = y; 
    }
    cout << ans << '\n';
}

int main() {
#ifdef LOCAL
    auto start = chrono::steady_clock::now();
    freopen("miku.in", "r", stdin);
    freopen("miku.out", "w", stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) MAIN();
#ifdef LOCAL
    auto end = chrono::steady_clock::now();
    cout << "\nqwq: " <<  chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
#endif
    return 0;
}