#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
//#define nONLINE_JUDGE
using namespace std;
// The interactor function provided by the grader
long long collisions(std::vector<long long> x);
// Global arrays for fast memory access, reused across hack() calls
int count_arr[1000005];
int freq[3000005];
bool used_arr[3000005];
int hack() {
int M = 3000000;
int K = 8000;
// Use a time-based seed to prevent any adversarial fixed test cases
static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// Initially, all numbers from 2 to 1,000,000 are candidates
vector<int> candidates;
candidates.reserve(1000000);
for (int n = 2; n <= 1000000; ++n) {
candidates.push_back(n);
}
int queries = 0;
int max_queries = 12;
// Filter candidates until 1 is left (or we hit our safety limit)
while (candidates.size() > 1 && queries < max_queries) {
vector<long long> X;
X.reserve(K);
// Generate a random set of distinct numbers
while (X.size() < K) {
long long x = uniform_int_distribution<long long>(1, M)(rng);
if (!used_arr[x]) {
used_arr[x] = true;
X.push_back(x);
}
}
// Clean up 'used_arr' cleanly without O(M) memset
for (long long x : X) used_arr[x] = false;
long long ans = collisions(X);
queries++;
vector<int> next_candidates;
// HYBRID LOGIC: Choose the fastest filtering method based on candidate count
if (candidates.size() > 500) {
// METHOD 1: Freq Array (O(K^2) to build, but O(M/n) to check candidates)
fill(freq, freq + M + 1, 0);
// Sorting helps the CPU hardware prefetcher predict memory access
sort(X.begin(), X.end());
for (int i = 0; i < K; ++i) {
int xi = X[i];
for (int j = i + 1; j < K; ++j) {
freq[X[j] - xi]++;
}
}
for (int n : candidates) {
long long c = 0;
for (int m = n; m <= M; m += n) {
c += freq[m];
}
if (c == ans) {
next_candidates.push_back(n);
}
}
}
else {
// METHOD 2: Modulo Simulation (O(C * K) where C is candidate count)
for (int n : candidates) {
long long c = 0;
for (long long x : X) {
int rem = x % n;
c += count_arr[rem];
count_arr[rem]++;
}
if (c == ans) {
next_candidates.push_back(n);
}
// Rollback count_arr cleanly
for (long long x : X) {
count_arr[x % n] = 0;
}
}
}
candidates = next_candidates;
}
if (!candidates.empty()) {
return candidates[0];
}
return 2; // Fallback
}
// =====================================================================
// LOCAL GRADER FOR TESTING
// This part will be ignored by Codeforces.
// =====================================================================
#ifdef nONLINE_JUDGE
int hidden_n;
long long total_cost = 0;
long long collisions(std::vector<long long> x) {
total_cost += x.size();
long long cols = 0;
vector<int> buckets(hidden_n, 0);
for (long long val : x) {
int rem = val % hidden_n;
cols += buckets[rem];
buckets[rem]++;
}
return buckets.clear(), cols;
}
int main() {
int t;
cout << "Enter number of test cases: ";
if (!(cin >> t)) return 0;
while (t--) {
cout << "Enter hidden n: ";
cin >> hidden_n;
total_cost = 0;
auto start = chrono::high_resolution_clock::now();
int result = hack();
auto end = chrono::high_resolution_clock::now();
double time_taken = chrono::duration_cast<chrono::milliseconds>(end - start).count();
cout << "Guessed n: " << result << " | Total Cost: " << total_cost << "\n";
cout << "Time taken: " << time_taken << " ms\n";
if (result == hidden_n) cout << "Correct!\n";
else cout << "Wrong Answer!\n";
cout << "-----------------------\n";
}
return 0;
}
#endif
