#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
int hack() {
ll l = 5e8 - 1, r = 1e9 + 1;
while(l + 1 < r) {
ll m = (l+r)/2;
// check if its in [l, m]
ll s = sqrt(m-l+1);
vector<ll> send;
for(ll i = 1; i <= s; i++) send.push_back(i);
ll right = m+1;
while(right > s) {
send.push_back(right);
if(right - s <= l) break;
right -= s;
}
if(collisions(send) > 0) r = m;
else l = m;
}
ll ans = r;
auto test = [&](int x){
while(true) {
if(ans % x != 0) return;
ans /= x;
if(collisions({1, ans+1}) == 0) {
ans *= x;
return;
}
}
};
ll p = 2;
while(p*p <= r) {
if(r % p == 0) {
while(r % p == 0) r /= p;
test(p);
}
p++;
}
if(r > 1) test(r);
return ans;
}
