#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;
		ll sum2 = (R + p - 1) / p, sum1 = (L + p - 1) / p;
		return (sum2 - sum1 < 0 ? 0 : 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 ((m & 1) == 0) {
		ans = ans + (((m ^ p - 1) - 1) % p == 0);
	}
	cout << ans << '\n';
}

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