#include<bits/stdc++.h>
using namespace std;
#define int long long


typedef vector<int> vi;

int n,k,m;

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tc=1;
    cin>>tc;
    while(tc--){
        cin>>k>>m;
        int best=numeric_limits<int>::max();
        for(int d=1;d<=1000;d++){
            n=d^k;
            int cont=m;
            for(int j=n+1;j<=n+d;j++){
                if(__gcd(n,j)==1){
                    cont--;
                }
            }

            if(cont==0 && __gcd(d,n)==1){
                best=min(best,n);
            }
        }
        if(best!=numeric_limits<int>::max()){
        cout<<best<<"\n";
        }else{
        cout<<-1<<"\n";
        }
        
    }



}