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

const int N=500;
typedef long long ll;

bool chk(ll n,int m,int k){
    if(!n)return 0;
    int cnt=0;
    for(int i=1;i<=k;++i){
        if(gcd(n,i)==1)
            ++cnt;
        if(cnt==m)
            return i==k;
    }
    return 0;
}

void solve(ll k,int m){
    ll ans=LLONG_MAX;
    for(int i=1;i<N;++i)
        if(chk(k^i,m,i))
            ans=min(ans,k^i);
    if(ans==LLONG_MAX)
        ans=-1;
    cout<<ans<<'\n';
    return;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    for(cin>>T;T --> 0;){
        ll k;int m;
        cin>>k>>m;
        solve(k,m);
    }
    return 0;
}