// #include<bits/stdc++.h>
// #define M 1005
// using namespace std;
// int n,m,col[M][M],siz[M*M],cnt,T,ans;
// char c[M][M];
// int dx[]={0,0,1,-1};
// int dy[]={1,-1,0,0};
// vector<pair<int,int> >e;
// void dfs(int x,int y){
// 	if(col[x][y]) return ;
// 	col[x][y]=cnt;siz[cnt]++;
// 	for(int i=0;i<4;++i){
// 		int nx=x+dx[i],ny=y+dy[i];
// 		if(nx<1||ny<1||nx>n||ny>m) continue;
// 		if(c[nx][ny]=='.') dfs(nx,ny);
// 	}
// }
// bool ckk(int x,int y){
// 	int nw=0;
// 	for(auto a:e){
// 		auto b=make_pair(a.first+x,a.second+y);
// 		if(b.first<1||b.second<1||b.first>n||b.second>m) return 0;
// 		if(c[b.first][b.second]=='O') return 0;
// 		if(nw!=0&&col[b.first][b.second]!=nw) return 0;
// 		nw=col[b.first][b.second];
// 	}
// 	return 1;
// }
// bool ck(int cl){e.clear();
// 	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(col[i][j]==cl) e.emplace_back(make_pair(i,j));
// 	for(int i=-n;i<=n;++i) for(int j=-m;j<=m;++j){
// 		if(i==0&&j==0) continue;
// 		if(ckk(i,j)) return 0;
// 	}
// 	return 1;
// }
// int main(){
// 	scanf("%d",&T);
// 	while(T--){
// 		scanf("%d%d",&n,&m);
// 		for(int i=1;i<=n;++i) scanf(" %s",c[i]+1);
// 		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(c[i][j]=='.'&&!col[i][j]) ++cnt,dfs(i,j);
// 		for(int i=1;i<=cnt;++i) if(ck(i)) ans+=siz[i];
// 		printf("%d\n",ans);
// 		for(int i=1;i<=cnt;++i) siz[i]=0;
// 		ans=cnt=0;
// 		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) col[i][j]=c[i][j]=0;
// 	}
// 	return 0;
// }
//A

#include<bits/stdc++.h>
using namespace std;
long long P,m,T,ans;
int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&P,&m);
		long long nw=0;
		for(int i=60;i>=0;--i){
			if((m>>i)&1){
				long long qwe=(((nw<<1)+(((P-1)>>i)&1))<<i)%P;
				ans+=((1ll<<i)-2+qwe)/P;
				if(qwe<=1) ans++;
			}
			nw<<=1;nw+=((m>>i)&1)+(((P-1)>>i)&1);
		}
		ans+=((m^(P-1))%P==1);
		printf("%lld\n",ans);ans=0;
	}
	return 0;
}