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

#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define pii pair<int, int>
#define vi vector<int>

#ifdef LOC
auto &operator << (auto &out, pair<auto, auto> a) {
	return out << "(" << a.st << ", " << a.nd << ")";
}

auto &operator << (auto &out, auto a) {
	out << "{";
	for (auto b : a)
		out << b << ", ";
	return out << "}";
}

void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }

#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif

typedef unsigned long long ull;
typedef long long ll;

ull modmul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}

ull modpow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}

bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
		s = __builtin_ctzll(n-1), d = n >> s;
	for (ull a : A) {   // ^ count trailing zeroes
		ull p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}

ull pollard(ull n) {
	auto f = [n](ull x) { return modmul(x, x, n) + 1; };
	ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
	while (t++ % 40 || __gcd(prd, n) == 1) {
		if (x == y) x = ++i, y = f(x);
		if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}

const int SMALL_ADD = 1e5;
const int SMALL_MAXN = 1e6 + SMALL_ADD;
const int SMALL_CHECK = 50;

int small_checks[SMALL_CHECK];
int small_divnum[SMALL_MAXN];
int smallest_divpow[SMALL_MAXN];

int small_primes[SMALL_MAXN];
int small_prime_cnt = 0;

vector<ull> rho_factor(ull n) {
	if (n == 1) return {};
	if (isPrime(n)) return {n};
	ull x = pollard(n);
	auto l = rho_factor(x), r = rho_factor(n / x);
	l.insert(l.end(), all(r));
	return l;
}

vector<ull> factor(ull n) {
	vector<ull> res;
	rep(i, 100) {
		while (n % small_primes[i] == 0) {
			res.push_back(small_primes[i]);
			n /= small_primes[i];
		}
	}
	auto oth = rho_factor(n);
	res.insert(res.end(), all(oth));
	return res;
}

ll largest_prime_factor(ull n) {
	auto factors = factor(n);
	return *max_element(all(factors));
}

ll count_factors(ll n) {
	auto factors = factor(n);
	map<ull, int> power;
	for (auto x : factors)
		power[x] += 1;
	ll num = 1;
	for (auto [x, w] : power)
		num *= w + 1;
	return num;
}

mt19937_64 rng(1410692137);

ll losuj(ll l, ll r) {
	return l + (rng() % (r - l + 1));
}

void verify_small() {
	set<vi> st;
	fwd(i, 1, SMALL_MAXN - SMALL_ADD + 1) {
		vi values;
		rep(j, SMALL_CHECK)
			values.push_back(small_divnum[i + small_checks[j]]);
		assert(st.find(values) == end(st));
		st.insert(values);
	}
}

void prep_small() {
	small_divnum[1] = 1;
	fwd(i, 2, SMALL_MAXN) {
		if (!small_divnum[i]) {
			smallest_divpow[i] = 1;
			small_divnum[i] = 2;
			small_primes[small_prime_cnt ++] = i;
		}
		rep(j, small_prime_cnt) {
			int prod = small_primes[j] * i;
			if (prod >= SMALL_MAXN)
				break;
			if (i % small_primes[j] == 0) {
				smallest_divpow[prod] = smallest_divpow[i] + 1;
				small_divnum[prod] = small_divnum[i] / (smallest_divpow[i] + 1) * (smallest_divpow[i] + 2);
			} else {
				smallest_divpow[prod] = 1;
				small_divnum[prod] = small_divnum[i] * 2;
			}
		}
	}
	rep(i, SMALL_CHECK)
		small_checks[i] = losuj(0, SMALL_ADD - 1);
	//verify_small();
}

ll solve_subtask_0(const ll N, const ll C) {
	vi asks(SMALL_CHECK);
	rep(i, SMALL_CHECK)
		asks[i] = Ask(small_checks[i]);
	fwd(i, 1, SMALL_MAXN - SMALL_ADD + 1) {
		bool fail = false;
		rep(j, SMALL_CHECK)
			if (asks[j] != small_divnum[i + small_checks[j]]) {
				fail = true;
				break;
			}
		if (!fail)
			return i;
	}
	assert(0);
	return -1;
}

bool inside_of(vector<ull> a, vector<ull> b) {
	sort(all(a));
	sort(all(b));
	while (sz(a)) {
		while (sz(b) && b.back() != a.back())
			b.pop_back();
		if (!sz(b))
			return false;
		a.pop_back();
		b.pop_back();
	}
	return true;
}

pair<ll, ll> lots_of_twos(const ll long N, const ll C) {
	ll init = losuj(1, N), init_divs = 2;
	int iters = 0;
	int ops = 0;
	while (largest_prime_factor(init_divs) < 5) {
		init += 1;
		iters += 1;
		init_divs = Ask(init);
		ops += 1;
	}
	vector<vector<ull> > need_guys = {
		{7},
		{3, 3},
		{2, 5},
		{11},
		{13},
		{3, 5},
		{17},
		{19},
		{3, 7},
		{2, 11},
		{23},
		{5, 5},
		{2, 13},
		{3, 3, 3},
		{2, 2, 7},
		{29},
		{31},
		{3, 11}
	};
	vector<ll> powers = {
		7,
		9,
		10,
		11,
		13,
		15,
		17,
		19,
		21,
		22,
		23,
		25,
		26,
		27,
		28,
		29,
		31,
		33
	};
	reverse(all(need_guys));
	reverse(all(powers));
	ll cur_power = largest_prime_factor(init_divs);
	while (sz(powers) && powers.back() <= cur_power)
		powers.pop_back();
	while (sz(powers)) {
		ll next_power = powers.back();
		powers.pop_back();
		ll dif_bits = next_power - cur_power;
		auto dudes = need_guys.back();
		need_guys.pop_back();
		rep(i, (1 << dif_bits)) {
			ll add_value = (1ll << (cur_power - 1));
			rep(j, dif_bits)
				if (i & (1 << j))
					add_value += (1ll << (cur_power + j));
			ll check_value = init + add_value;
			ll check_divs = Ask(check_value);
			ops += 1;
			if (inside_of(dudes, factor(check_divs))) {
				init = check_value;
				init_divs = check_divs;
				cur_power = next_power;
				break;
			}
		}
		if (cur_power == next_power)
			continue;
		return {-1, -1};
	}
	return {init, cur_power};
}

ll solve_subtask_1(const ll N, const ll C) {
	pair<ll, ll> big = {-1, -1};
	while (big.st == -1)
		big = lots_of_twos(N, C);
	ll pwr = big.nd - 1;
	ll value = 0;
	vector<ll> guesses;
	while (true) {
		value += (1ll << pwr);
		ll my_guess = value - big.st;
		if (my_guess < 0)
			continue;
		if (my_guess > N)
			break;
		guesses.push_back(my_guess);
	}
	vector<ll> tmp;
	while (sz(guesses) > 1) {
		tmp.clear();
		ll max_guess = *max_element(all(guesses));
		ll off = losuj(0, C - max_guess - 10);
		ll divisors = Ask(off);
		for (auto my_guess : guesses)
			if (count_factors(my_guess + off) == divisors)
				tmp.push_back(my_guess);
		swap(tmp, guesses);
	}
	return guesses.back();
}

ll solve(const ll N, const ll C, const int subtask) {
	if (subtask == 0)
		return solve_subtask_0(N, C);
	return solve_subtask_1(N, C);
}

int main() {
  	int t = GetT();
	ll n = GetN();
	int q = GetQ();
 	ll c = GetC();
	int subtask = -1;
	if (n <= 1e6 + 10)
		subtask = 0;
	else
		subtask = 1;
	prep_small();
  	rep(i, t)
		Answer(solve(n, c, subtask));
  	return 0;
}