#include <bits/stdc++.h>
#include <math.h>

//#pragma GCC optimize("O3,unroll-loops")

using namespace std;
	
#ifndef ONLINE_JUDGE
	#define _GLIBCXX_DEBUG
	#define local_shit freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout);
#else
	#define local_shit
#endif
		
// io macros
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr);
#define make_test_shit freopen("inp.txt", "w", stdout);

// c++ short types
#define Int long long
#define vt vector
#define pi pair<int, int>

// code macros
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ins insert
#define mp make_pair

// loops macros
#define each(x, a) for(auto &x: a)

// some functions
template<typename T>
void umax(T &a, const T &b) { a = max(a,b); }
template<typename T>
void umin(T &a, const T &b) { a = min(a,b); }
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
template<typename T>
T firsttrue(T l, T r, function<bool(T)> f) {
	while(r - l > 1) {
		T m = (l+r)/2;
		if(f(m)) {
			r = m;
		} else {
			l = m;
		}
	}
	return r;
}
template<typename T>
T lasttrue(T l, T r, function<bool(T)> f) {
	while(r - l > 1) {
		T m = (l+r)/2;
		if(f(m)) {
			l = m;
		} else {
			r = m;
		}
	}
	return l;
}

long long gcd(long long a, long long b) {
	while(b) {
		b = a % b; swap(a,b);
	}
	return a;
}

void solver() {
	long long k, m; cin >> k >> m;
	long long res = -1;
	for(long long d = 0; d <= 1000; ++d) {
		long long n = k ^ d;
		int ord = 0;
		for(long long i = 0; i <= 1e4; ++i) {
			ord += __gcd(i,n) == 1;
			if(ord == m) {
				if(i == d) {
					if(res == -1) {
						res = n;
					}
					umin(res, n);
				}
				break;
			}
		}
	}
	cout << res << '\n';
}

int main()
{
	fastio;
	int tt = 1;
	cin >> tt;
	for(int t = 0; t < tt; ++t) {
    solver();
	}
	//whattime();
	return 0;
}