#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
ll read(){
    ll X = 0 ,r = 1;
    char ch = getchar();
    while(!isdigit(ch) && ch != '-') ch = getchar();
    if(ch == '-') r = -1,ch = getchar();
    while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
    return X*r;
}
void solve(){
	__int128 P = read(),m = read(),t = m/P;
	if(t < 0) t = -1;
	ll ans = t+1;
	for(ll i=1;i<=30;i++){
		__int128 x = t+i;
		if(((x*P+1)^(P-1)) <= m) ans++;
	}
	cout << ans << "\n";
}
int main(){
	int T = read();
	while(T--) solve();	
	return 0;
}