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

void ps(int x) {
	for (int i = 31; i >= 0; i --) {
		cout << ((x >> i) & 1);
	}
	cout << '\n';
}


int get(int x) {
	for (int i = 31; i >= 0; i --) {
		//cout << ((x >> i) & 1);
		if ((x >> i) & 1) {
			return i;
		}
	}
	return 0;
}

void solve() {
	ll p , m;
	cin >> p >> m;
	// x = (k * p + 1) ^ p
	//ps(p);
	// if (m == 0) {
	// 	cout << 1 << '\n';
	// 	return;
	// }
	int u = get(m);
	int ans = 0;
	for (int i = 0;; i ++) {
		ll x = i * p + 1 ^ (p - 1);
		if (x <= m) ans ++; 
		if (get(x) > u) {
			//cout << "i = " << i << '\n';
			break;
		}
		
	}
	cout << ans << '\n';
}

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