#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
int T;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>T;
    while(T){
        --T;
        ll p,m;
        cin>>p>>m;
        ll l=-1,r=(m/p)+3;
        while(l<r){
            ll mid=(l+r+1)/2;
            ll u=(p*mid+1)^(p-1);
            if(u<=m)l=mid;
            else r=mid-1;
        }
        ll ans=l+1;
        if(l<=3){
            ans=0;
            fo(k,0,6){
                ll u=(p*k+1)^(p-1);
                ans+=(u<=m);
            }
        }
        else {
            ans-=5;
            l-=5;
            fo(k,1,5){
                ll u=(p*(k+l)+1)^(p-1);
                ans+=(u<=m);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}