#include<bits/stdc++.h>
using namespace std;
long long p,m;
long long calc(long long st,long long ed){
	if(ed<st)
		return 0;
	long long l;
	if(st-2<0)
		l=0;
	else
		l=(st-2)/p+1;
	long long r=(ed-1)/p+1;
	return r-l;
}
void solve(){
	cin>>p>>m;
	if(m==0){
		if(p==2){
			cout<<1<<endl;
		}
		else
			cout<<0<<endl;
		return;
	}
	long long ans=0,st=0,ed;
	for(int i=62;i>=0;--i){
		if((1ll<<i)&m){		
			if((1ll<<i)&p){
				st+=(1ll<<i); 
			}
			ed=(__int128)st+(1ll<<i)-1;//cout<<st<<" "<<ed<<endl;
			ans+=calc(st,ed);
			if((1ll<<i)&p){
				st-=((1ll)<<i); 
			} 
			else
				st+=((1ll)<<i);
			cout<<ans<<endl; 
		}
		else{
			if((1ll<<i)&p){
				st+=((1ll)<<i); 
			} 
		}

	}
	cout<<ans<<endl;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		solve();
	} 
}