#include "hack.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int hack() {
ll l = (ll)5e8, r = (ll)1e9 + 1;
while (l < r) {
ll mid = (l + r) / 2;
ll N = mid - l + 1;
ll x = (ll)sqrt(N);
set<ll> A;
for (int i = 1; i <= x; i++) A.emplace(i);
for (int i = l + x; i <= mid; i += x) A.emplace(i);
A.emplace(mid + 1);
vector<ll> Q;
for (auto &e : A) Q.emplace_back(e);
if (collisions(Q)) r = mid;
else l = mid + 1;
}
vector<ll> p;
ll t = l;
for (ll i = 2; i * i <= t; i++) {
if (t % i == 0) p.emplace_back(i);
while (t % i == 0) t /= i;
}
if (t > 1) p.emplace_back(t);
for (auto &e : p) {
while (l % e == 0) {
vector<ll> Q = {1LL, l / e + 1};
if (collisions(Q)) l /= e;
else break;
}
}
return (int)l;
}
