#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<random>
#include<ctime>
using namespace std;
#define re int
#define ll long long
inline ll read(){
    ll x=0,ff=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
    return x*ff;
}
inline int hbit(ll x){
	for(re i=59;i>=0;i--)
		if((x>>i)&1)return i;
	return 23333;
}
int main(){
	int t=read(),x,y;ll p,m,ss;
	while(t--){
		p=read();m=read();
		if(m==0){
			if(p==2)puts("1");
			else puts("0");
			continue;
		}
		if(p==2&&m<=3){
			if(m<2)puts("1");
			else puts("2");
			continue;
		}
		x=hbit(p-1);y=hbit(m);
		if(x>=y){
			if(m>=p)puts("1");
			else puts("0");
			continue;
		}
		ll u=m&(((1ll<<(y+1))-1)^((1ll<<(x+1))-1));
		ll v=m-u;
		ss=(u-1)/p+(((u-1)%p)>=1);
		ll _u=u;u%=p;u^=((p-u)%p)^(p-1);
		if(u<=v)ss++;
		_u%=p;
		if(_u+p<(1ll<<(x+1))){
			_u^=((p-_u)%p+p)^(p-1);
			if(_u<=v)ss++;
		}
		printf("%lld\n",ss);
	}
    return 0;
}