#include<bits/stdc++.h>
#define ll unsigned 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;
    }
    // reverse(idxm+1,idxm+1+k);reverse(idxp+1,idxp+1+n);
    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;
                if(l==0) l=1;
                // cout<<l<<' '<<p<<endl;
                if(r>=1) ans+=max((ll)0,(r-1)/p-((l-1)/p+((l-1)%p==0?0:1))+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;
}