#include "hack.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int qry(int x) {
vector <ll> v;
int x2 = x;
for (int i = 2; i <= sqrt(x2); i++) {
while (x2 % i == 0) v.emplace_back(i), x2 /= i;
}
if (x2 != x && x2 > 1) v.emplace_back(x2);
int r = -1;
for (auto &e : v) {
if (e == r) continue;
if (collisions({1, x/e+1})) x /= e;
else r = e;
}
return x;
}
int hack() {
ll L = 5e8, R = 1e9;
while (L < R) {
// cerr << L << ' ' << R << '\n';
ll w = sqrt((R-L)/2);
ll m = w*w;
// cerr << m << '\n';
if (m == 0) break;
vector <ll> k;
for (int i = 1; i <= w; i++) k.emplace_back(i);
for (int i = 1; i <= w; i++) k.emplace_back(L + i * w);
// cerr << "Q "; for (auto &e : k) cout << e << ' '; cout << '\n';
if (collisions(k)) R = L + m;
else L = L + m;
}
// cout << "LR " << L << ' ' << R << '\n';
for (int i = L; i <= R; i++) {
// cout << "COL " << 1 << ' ' << i+1 << '\n';
if (collisions({1, i})) return qry(i-1);
}
return 1e9;
}
