#include <bits/stdc++.h>
#ifndef LOCAL
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
using namespace std;
#define int long long
#define tmp template <class T>
#define vec vector
#define i32 int32_t
#define i64 int64_t
using pii = pair<int, int>;
// #define F(...) [&](auto&& x) { __VA_ARGS__; }
// #define G(...) [&](auto&& a, auto&& b) { __VA_ARGS__; }
#define len(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rev(x) rbegin(x), rend(x)
#define X first
#define Y second
int collisions(vec<int> x);
#ifdef LOCAL
int n;
int calls;
int collisions(vec<int> a) {
calls += a.size();
int ans = 0;
map<int, int> f;
for (int x: a) {
ans += f[x % n]++;
}
return ans;
}
#endif
signed hack() {
for (int i = 2; i <= 500'000; i++) {
if (collisions({i, i * 2}) == 1) {
return i;
}
}
return 0;
}
#ifdef LOCAL
signed main() {
cin.tie(nullptr)->sync_with_stdio(0);
for (int i = 2; i <= 100'000; i++) {
n = i;
calls = 0;
int ans = hack();
if (n == ans && calls <= 1000'000) {
cout << "Done " << i << endl;
} else {
cout << n << " " << ans << " " << calls << endl;
}
}
}
#endif
