#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define per(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fopen(x) { freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout); }
#define fi first
#define se second
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<char> VC;
typedef vector<pair<int, int>> VP;
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {return l + mrand() % (r - l + 1);}
const ll inf = 1e9 + 5, llf = 1e18 + 5;
///////////////////////////////////////////////////////////////////

void solve(){
    ll p, m;  cin >> p >> m;
    ll ans = 0;
    auto calcu = [&] (ll l, ll r) -> ll {
        l = ceil(1.0 * (l - 1) / p), r = floor(1.0 * (r - 1) / p);
        if(r < 0) return 0;
        if(l < 0) l = 0;
        cerr << l << " " << r << "\n";
        return max(0ll, r - l + 1);
    };
    per(i, 60, 0) {
        if(m >> i & 1) {
            ll l = m >> i;
            l --;
            l ^= (p - 1) >> i;
            l <<= i;
            ll r = l + (1ll << i) - 1;        
            ans += calcu(l, r);
        } 
    }
    ans += calcu(m ^ (p - 1), m ^ (p - 1));
    cout << ans << "\n";
}

signed main() {
    IOS;
    int T;  cin >> T;
    while(T --){
        solve();
    }
    
    return 0;
}