#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll p, m;
void solve() {
	cin >> p >> m;
	ll pp = p - 1;
	ll sum = 0, ans = 0;
	for (int i = 60; i >= 0; i--) {
		ll k = (1ll << i), mx, mn, L, R;
		if (i == 0) {
			mn = sum, mx = sum;
			if ((k & pp) || (k & m)) mx++;
			if ((k & pp) && !(k & m)) mn++;
			mn = max(0ll, mn - 1), mx = max(0ll, mx - 1);
			L = (mn / p) + ((mn % p) ? 1 : 0), R = mx / p;
			ans += (R - L + 1);
		} else {
			if ((k & pp) && (k & m)) {
				mn = sum + k, mx = sum + k + k - 1;
				mn = max(0ll, mn - 1), mx = max(0ll, mx - 1);
				L = (mn / p) + ((mn % p) ? 1 : 0), R = mx / p;
				ans += (R - L + 1);
			} else if (k & m) {
				mn = sum, mx = sum + k - 1;
				mn = max(0ll, mn - 1), mx = max(0ll, mx - 1);
				L = (mn / p) + ((mn % p) ? 1 : 0), R = mx / p;
				ans += (R - L + 1);
				sum += k; 
			} else if (k & pp) {
				sum += k;
			}
		}
//		cout << mn << " " << mx << " " << sum << "\n";
	}
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}