#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;
	if(ed-1<0)
		r=0;
	else
		r=(ed-1)/p+1;
//	cout<<l<<" "<<r<<endl;
	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){	
			long long d=0;
			if((1ll<<i)&p)
				d=1;
		//	cout<<"&"<<(st+(d<<i))<<endl;
			ans+=calc(st+(d<<i),(__int128)st+(d<<i)+(1ll<<i)-1);
			if((1ll<<i)==(m&(-m))){
		//		cout<<"*"<<(st+((d^1)<<i))<<endl;
				ans+=calc(st+((d^1)<<i),st+((d^1)<<i));
				break;
			}
			else{
				st+=(((d^1)<<i));
			}
		//	cout<<ans<<endl; 
		}
		else{
			if((1ll<<i)&p){
				st+=((1ll)<<i); 
			} 
		}

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