#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;
#define CRP(t, x) const t &x
#define OPL(t, x) bool operator<(CRP(t, x)) const
#define FIL(x, v) memset(x, v, sizeof(x))
#define CLR(x) FIL(x, 0)
#define NE1(x) FIL(x, -1)
#define INF(x) FIL(x, 0x3f)
typedef long long ll, i64;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll f(ll n, ll m)
{
    ll x = n;
    do
        if (gcd(++x, n) == 1) m--;
    while (m);
    return x;
}
int main()
{
    ll T, k, m;
    scanf("%lld", &T);
    while (T--)
    {
        scanf("%lld%lld", &k, &m);
        bool flag = true;
        for (ll n = 1; n < 10000; n++)
            if (((f(n, m) - n) ^ n) == k)
            {
                printf("%lld\n", n);
                flag = false;
                break;
            }
        if (flag) puts("-1");
    }
    return 0;
}