#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=1e5+5;
void solve() {
    int p,m;
    cin>>p>>m;
    int t=p-1;
    if(p==2) 
    {
        cout<<m/2+1<<"\n";
    } 
    else 
    {
        int sum=0;
        int yt=0;
        for(__int128 i=0; i<100000000; i++) 
        {
            if(((i*p+1)^t)<=m) 
            {
                sum++;
            } 
            else 
            {
                if(yt) break;
                else yt++;
            }
        }
        cout<<sum<<endl;
    }
}
signed main() {
    int T=1;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) 
    {
        solve();
    }
}