#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;
const int N = 1e9;
const int N2 = 5e8;
const int k = 7700;
const int b2 = N2 / k;
const int b = N / k;
int hack(){
vector<ll> s(k);
for(int i = 0; i < k; i++) s[i] = i + 1;
function<ll(int, int)> get = [&](int tl, int tr){
vector<ll> r;
for(int i = tl; i <= tr; i++){
if((i + 1) * k <= k) continue;
r.pb((i + 1) * k);
}
for(int i : s) r.pb(i);
return collisions(r);
};
function<int(int)> fin_get = [&](int x){
// [x * k, x * (k + 1))
int tl = 1, tr = k;
while(tr > tl){
// cout << tl << ' ' << tr << ' ';
int tm = (tl + tr + 1) / 2;
vector<ll> r = {k * (x + 1)};
for(int i = tm; i <= tr; i++){
if(k * (x + 1) <= i) continue;
r.pb(i);
}
ll ok = collisions(r);
// cout << ok << endl;
if(ok)
tl = tm;
else
tr = tm - 1;
}
return (x + 1) * k - tl;
};
int tl = b2, tr = b;
while(tl < tr){
int tm = (tl + tr) / 2;
if(get(tl, tm))
tr = tm;
else
tl = tm + 1;
}
int ans = fin_get(tl);
int res = ans;
for(int i = 2; i * i <= ans; i++){
while(ans % i == 0){
if(collisions({1ll, res / i + 1})){
ans /= i;
res /= i;
}
else
break;
}
while(ans % i == 0){
ans /= i;
}
}
if(ans > 1 && collisions({1ll, (ll) res / ans + 1}))
res /= ans;
return res;
}
