// [5B] Dzielniki, Kamil Debowski
#include <bits/stdc++.h>
using namespace std;
#include "dzilib.h"
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

// Rho Pollarda, UW / Blazej Magnowski
using ll = long long;
//vector<ll> witness = {2, 7, 61}; // < 4759123141
vector<ll> witness = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // < 2^64
ll mnoz(ll a, ll b, ll mod) {
  return (__int128(a)*b)%mod;
}
ll pot(ll a, ll b, ll mod) {
  ll res = 1;
  while (b) {
    if (b&1)
      res = mnoz(res,a,mod);
    a = mnoz(a,a,mod);
    b /= 2;
  }
  return res;
}
bool test(ll n) {
  if (n == 2)
    return true;
  if (n < 2 || n%2 == 0)
    return false;
  
  ll d = n-1;
  ll s = 0;
  while (d%2 == 0) {
    d /= 2;
    ++s;
  }
  for (auto i: witness) if (i%n) {
    ll x = pot(i,d,n);
    if (x != 1) {
      bool zlozona = true;
      for (int j = 0; j < s; j++) {
        if (x == n-1) {
          zlozona = false;
          break;
        }
        x = mnoz(x, x, n);
      }
      if (zlozona)
        return false;
    }
  }
  
  return true;
}
ll nwd(ll a, ll b) {
  return a ? nwd(b%a,a) : b;
}
ll f(ll x, ll mod, ll c) {
  ll y = mnoz(x,x,mod) + c;
  if (y > mod)
    y -= mod;
  return y;
}
void rho(ll n, vector<ll> &v) {
  if (n <= 1) return;
  if (test(n)) {
    v.push_back(n);
    return;
  }
  
  ll c = 1;
  while(true) {
    ll x = 2, y = 2, d = 1;
    while (d == 1) {
      x = f(x,n,c);
      y = f(f(y,n,c),n,c);
      d = nwd(abs(x-y),n);
    }
    if (d < n) {
      rho(d, v);
      rho(n/d,v);
      return;
    }
    ++c;
  }
}
int countDivisors(ll n) {
	vector<ll> v;
  int BLOK = 100;
  for (int i = 2; i <= BLOK; i++) while (n%i == 0) {
    n /= i;
    v.push_back(i);
  }
  
  rho(n,v);
  sort(v.begin(),v.end());
  int divisors = 1;
  for (int i = 0; i < (int) v.size(); i++) {
	  int cnt = 1;
	  while (i + 1 < (int) v.size() && v[i] == v[i+1]) {
		  cnt++;
		  i++;
	  }
	  divisors *= cnt + 1;
  }
  return divisors;
}

mt19937 GEN(98657256);

ll r(ll a, ll b) {
	return uniform_int_distribution<long long>(a, b)(GEN);
}



void test() {
	map<long long, int> memo;
	auto query = [&](long long x) {
		assert(0 <= x && x <= GetC());
		int tmp = Ask(x);
		memo[x] = tmp;
		return tmp;
	};
	ll shift = r(0LL, GetN() / 10);
	
	// find divisible by 4, not by 8
	{
		vector<bool> can(8, true);
		int candidates = 8;
		for (int rep = 0; candidates > 1; rep++) {
			for (int i = 0; i < 8 && candidates > 1; i++) {
				if (can[i] && query(shift + i + rep * 8) % 3) {
					can[i] = false;
					--candidates;
				}
			}
		}
		for (int i = 0; i < 8; i++) {
			if (can[i]) {
				shift += i;
			}
		}
	}
	
	long long d = 0;
	for (int expo = 4; (1LL << expo) < GetN() * 5; expo += 2) {
		d = (1LL << expo);
		// I'm divisible by d/4, not by d/2
		shift += d / 4;
		// I'm divisible by d/2
		
		if (d / 2 > GetN() / 100) {
			// d/2 | HIDDEN+shift
			set<long long> s;
			for (ll maybe = -shift; maybe <= GetN() && (int) s.size() <= 1; maybe += d / 2) {
				if (maybe >= 1) {
					bool ok = true;
					for (auto p : memo) {
						if (countDivisors(maybe+p.first) != p.second) {
							ok = false;
							break;
						}
					}
					if (ok) s.insert(maybe);
				}
			}
			// debug() << "HACK = " <<  imie(s);
			assert(!s.empty());
			if ((int) s.size() == 1) {
				ll answer = *s.begin();
				Answer(answer);
				// assert(answer == HIDDEN);
				return;
			}
		}
		
		// want: divisible by d, not by 2*d
		auto good = [&](long long x) {
			return query(x) % (expo + 1) == 0;
		};
		if (expo + 1 <= 9) { // 5,7,9 -> full deterministic check
			vector<bool> can(4, true);
			int candidates = 4;
			for (int rep = 0; candidates > 1; rep++) {
				for (int i = 0; i < 4 && candidates > 1; i++) {
					if (can[i] && !good(shift + d / 2 * i + rep * 2 * d)) {
						can[i] = false;
						candidates--;
					}
				}
			}
			for (int i = 0; i < 4; i++) {
				if (can[i]) {
					shift += i * d / 2;
					// assert(good(shift));
				}
			}
		}
		else { // 11+ -> randomized check, with extra safety for some values
			for (int rep = 0; rep < 3; rep++) { // 4th is ok for sure
				int checks = 1;
				for (int x : {5, 5, 7, 7, 9, 9, 11, 13, 15, 21, 25, 27, 33}) { // 13 is least important, next would be 17
					if (expo + 1 == x) {
						checks++;
					}
				}
				bool ok = true;
				for (int j = 0; j < checks; j++) {
					if (!good(shift + j * 2 * d)) {
						ok = false;
						break;
					}
				}
				if (ok) {
					break;
				}
				shift += d / 2;
			}
		}
		
		// if (! ((HIDDEN + shift) % (d) == 0)) { cerr << "expo+1 = " << expo+1 << endl; assert(false); }
		// if (!((HIDDEN + shift) % (2 * d) != 0)) { cerr << "expo+1 = " << expo+1 << " case#2" << endl; assert(false); }
	}
	// I'm divisible by d
	ll answer = d - shift;
	Answer(answer);
}

int main() {
	int TT = GetT();
	while (TT--) {
		test();
	}
}