#include"hack.h"
#include<bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define ll long long
using namespace std;
int hack(){
ll l=2,r=1e9;
while(l+1<r) {
ll m=(l+r)>>1,s=1000,pos=m+1;
vector<ll>q;
for(ll i=1;i<=s&&i<=m;i++)q.push_back(i);
while(pos>s&&q.size()<1000) {
q.push_back(pos);
if(pos-s<=l)break;
pos-=s;
}
collisions(q)>0?r=m:l=m;
}
ll ans=r;
for(ll p=2;p*p<=ans&&p<=1000;p++)if(ans%p==0) {
while(!(ans%p)) {
ll k=ans/p;
if(!collisions({1,k+1}))ans=k;
else break;
}
}
return(int)ans;
}
