#include<bits/stdc++.h>
using namespace std;
 #define ll long long 
#define int unsigned long long
#define INF 0x3f3f3f3f
const int N=1e5+5;
#define pb push_back
#define pii pair<int,int>
const int mod=998244353;
 ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1){ans*=a;ans=ans%mod;}a=a*a;a%=mod;b>>=1;}return ans;}
 ll gcd(ll a,ll b){ll t=a%b;while(t){a=b;b=t;t=a%b;}return b;}
 ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
 ll get_inv(ll x){return ksm(x,mod-2);}
void solve()
{
 		int p,m;
 		cin>>p>>m;
 		if(p==2)
 		{
 			cout<<m/2+1<<endl;
 			return ;
 		}
 		int k=m/p;
 		int ans=k;
 		for(int i=k;i<=5000;i++)
 		{
 			int l=(i*p+1)^(p-1);
 			if(l<=m)
 			{ans++;}
 		}
 		cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _;cin>>_;while(_--)
    solve();
}