#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=5e8-1,r=1e9+1,p=2;
while(l+1<r) {
ll m=(l+r)/2,s=sqrt(m-l+1);
vector<ll>q;
for(ll i=1;i<=s;i++)q.push_back(i);
ll ri=m+1;
while(ri>s) {
q.push_back(ri);
if(ri-s<=l)break;
ri-=s;
}
collisions(q)>0?r=m:l=m;
}
ll ans=r,temp=r;
while(p*p<=temp) {
if(!(temp%p)) {
while(!(temp%p))temp/=p;
while(1) {
if(ans%p)break;
ans/=p;
if(!collisions({1,ans+1})) {ans*=p;break;}
}
}
p++;
}
if(temp>1) {
while(1) {
if(ans%temp)break;
ans/=temp;
if(!collisions({1,ans+1})) {ans*=temp;break;}
}
}
return(int)ans;
}
