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

const int lmt = 800;

bool check(ll n, ll m, ll k) {
    int cnt = 0;
    for (int d=1;d<=lmt;d++) {
        if (gcd(n, d) == 1) {
            cnt += 1;
        }
        if (cnt == m) {
            if ((d^n) == k) return true;
            else return false;
        }
    }
    return false;
}
void solve() {
    ll k, m;
    cin>>k>>m;
    
    ll ans = 8e18;
    for (ll d=1;d<=lmt;d++) {
        ll n = (k^d);
        if (check(n, m, k)) {
            ans = min(ans, n);
        }
    }
    if (ans > 7e18) {
        printf("%d\n", -1);
    }else{
        printf("%lld\n", ans);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}