#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll p,m,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;
    M=m;
    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--;
                // cout<<l<<' '<<p<<endl;
                if(r>=0) ans+=max(0ll,r/p-(ll)max((long double)0,ceil((long double)l/(long double)p))+1);
                // cout<<fixed<<setprecision(10)<<(double)l/(double)p<<endl;
                if(idxp[i]==0) sum=sum*2+1;
                else sum=sum*2;
            }
        }
    }
    if((m^(p-1))%p==1) 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;
}