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


void solve() {
	ll p, m;
	cin >> p >> m;

	ll now = 0;
	auto cal = [&](int x) -> ll {
		// L <= kp < R
		ll L = now - 1, R = now + (1 << x) - 1;
		//cout << L << ' ' << R << '\n';
		ll sum2 = (R + p - 1) / p, sum1 = (L + p - 1) / p;
		//cout << sum1 << ' ' << sum2 << '\n';
		return sum2 - sum1;
	};

	ll ans = 0;
	for (int i = 63; i >= 0; i --) {
		if ((m >> i) & 1) {
			ans = ans + cal(i);
			now = now + (1 << i);
		}
	}
	if (p == 2) {
		ans ++;
	}
	cout << ans << '\n';
}

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