#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int p,m;
    cin>>p>>m;
    int cnt=0;
    int idx=m/p;
    if(p%2==0){
        if(m<p-2)cnt=-1;
        else cnt=0;
    }else{
        if(m<p)cnt=-1;
        else cnt=0;
    }
    if(((p-1)^(idx*p+1))<=m){

    }else{
        cnt--;
    }
    if(((p-1)^((idx+1)*p+1))<=m){
        cnt++;
    }
    if(((p-1)^((idx+2)*p+1))<=m){
        cnt++;
    }
    if(((p-1)^((idx-1)*p+1))<=m){
        cnt++;
    }
    if(((p-1)^((idx-2)*p+1))<=m){
        cnt++;
    }
    cnt+=(idx-1);
    if(cnt<0)cnt=0;
    cout<<cnt<<endl;
}
signed main() {
    std::ios::sync_with_stdio(false);

    int t;
    cin>>t;
    while(t--)solve();
//    solve();
    return 0;
}