#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef unsigned long long ull;
const ull MAX=4e18;
const int D=500;
void solve(){
	int p,m;cin>>p>>m;
	ull l=0,r=MAX/p;
	while(l<=r){
		int mid=(l+r)>>1;
		int num=(1+r*p)^(p-1);
		if(num>m) r=mid-1;
		else l=mid+1;
	}
	ull ind=r;
	int ans=0;
	l=ind-D,r=ind+D;
	if(l<0) l=0;
	if(r>MAX/p) r=MAX/p;
	for(int i=l;i<=r;i++){
		int num=(1+i*p)^(p-1);
		if(num<=m) ans++;
	}
	ans+=l;
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}