#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e9;
int ans(int l, int r) {
while (l < r) {
int m = (l + r) >> 1;
int c = sqrtl(m - l + 1);
vector<int> q;
for (int i = 1; i <= c; ++i) q.push_back(i);
for (int i = l + c; i <= m; i += c) q.push_back(i);
if (m + 1 > c) q.push_back(m + 1);
if (collisions(q)) {
r = m;
} else {
l = m + 1;
}
}
vector<int> divs;
divs.push_back(l);
for (int i = 2; i * i <= l; ++i) {
if (l % i == 0) {
divs.push_back(i);
if (i * i != l) divs.push_back(l / i);
}
}
sort(divs.begin(), divs.end());
vector<int> primes;
for (int d : divs) {
bool is_prime = true;
for (int p : primes) {
if (d % p == 0) {
is_prime = false;
break;
}
}
if (is_prime) primes.push_back(d);
}
int prev_l = -1;
while (l != prev_l) {
prev_l = l;
for (int p : primes) {
if ((l / p) * p == l) {
if (collisions({1, (l / p) + 1})) {
l /= p;
break;
}
}
}
}
return l;
}
signed hack() {
return ans(inf / 2, inf);
}
