#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p,m;
ll ans;
int n,k;
int idxp[105],idxm[105];
ll pw[105];
void solve(){
    cin>>p>>m;
    ll t=p-1;
    n=0;ans=0;
    while(t){
        idxp[++n]=t%2;
        t/=2;
    }
    k=0;
    while(m){
        idxm[++k]=m%2;
        m/=2;
    }
    ll sum=0;
    for(int i=max(n,k);i>=1;i--){
        if(i>k){
            sum=sum*2+idxp[i];
        }
        else{
            if(idxm[i]==0){
                if(idxp[i]==1) sum=sum*2+1;
                else sum=sum*2;
            }
            else{
                ll l=(sum*2+idxp[i])*pw[i-1],r=(sum*2+idxp[i])*pw[i-1]+pw[i-1]-1;
                l--;r--;
                ans+=r/p-ceil((double)l/(double)p)+1;
                if(idxp[i]==0) sum=sum*2+1;
                else sum=sum*2;
            }
        }
    }
    if((m-1)%p==0) ans++;
    if((1LL^(p-1))<=m) ans++; 
    cout<<ans<<endl;
}
int main(){
    int T;
    pw[0]=1;
    for(int i=1;i<=69;i++) pw[i]=pw[i-1]*2;
    cin>>T;
    while(T--)
        solve();
    return 0;
}