#include <bits/stdc++.h>
long long collisions(std::vector<long long> x);
int hack() {
int l = 5e8, r = 1e9;
while (l < r) {
int m = std::midpoint(l, r);
int b = std::sqrt(m - l + 1);
std::vector<long long> q;
for (int i = 1; i <= b; ++i) {
q.push_back(i);
}
for (int i = l + b; i <= m; i += b) {
q.push_back(i);
}
if (m + 1 > b) {
q.push_back(m + 1);
}
if (collisions(q)) {
r = m;
} else {
l = m + 1;
}
}
std::vector<int> div = {l};
for (int i = 2; i * i <= l; ++i) {
if (l % i == 0) {
div.push_back(i);
if (i * i != l) {
div.push_back(l / i);
}
}
}
std::sort(div.begin(), div.end());
std::vector<int> primes;
for (int i = 0; i < div.size(); ++i) {
bool prime = true;
for (auto &p : primes) {
if (div[i] % p == 0) {
prime = false;
}
}
if (prime) {
primes.push_back(div[i]);
}
}
int prev_l = -1;
while (l != prev_l) {
prev_l = l;
for (auto &p : primes) {
if ((l / p) * p == l and collisions({1, l / p + 1})) {
l /= p;
break;
}
}
}
return l;
}
