1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "dzilib.h"
#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;

void solve(){
	mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

	ll N = GetN();

	ll G = uniform_int_distribution<ll>(N / 100, N / 50)(mt);
	vector<pair<ll, ll> > results;
	int nq = 0;
	auto my_ask = [&](ll x) -> ll {
		nq++;
		ll v = Ask(x + G);
		results.push_back({x, v});
		return v;
	};
	auto my_answer = [&](ll x) -> void {
		Answer(x - G);
	};
	auto v2 = [&](ll x) -> ll {
		if(x == 0) return 64;
		return __builtin_ctzll(x);
	};
	ll C = GetC() - G; // max X

	ll res = 0; // x % mod = res
	ll b = 0;
	while(true){
		ll mod = ll(1) << b;
		if(mod > N + G) break;
		ll X = 5;
		vector<bool> ok(1 << X, true);
		for(auto [v, d] : results){
			for(int i = 0; i < (1 << X); i++){
				ll f = (res + i * mod) + v;
				ll v2_f = v2(f);
				if(v2_f >= b + X) continue;
				if(d % (v2_f + 1) != 0){
					ok[i] = false;
				}
			}
		}
		vector<bool> ok_mod_2(2, false);
		for(int i = 0; i < (1 << X); i++) if(ok[i]) ok_mod_2[i&1] = true;

		bool done = false;
		for(int s : {0, 1}){
			if(!ok_mod_2[1^s]){
				res += s * mod;
				b++;
				done = true;
				break;
			}
		}
		if(done){
			// cerr << "x is " << res << " mod " << mod << '\n';
			continue;
		}

		ll max_mod_mult = C / mod / 2;
		ll z = uniform_int_distribution<ll>(1, max_mod_mult)(mt);
		my_ask(mod - res + mod * z);
	}
	ll ans = res;
	my_answer(res);
	// cerr << "answer " << ans << " queries " << nq << '\n';
}
int main() {
	int T = GetT();
	while(T--) solve();
	return 0;
}