#include"hack.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e9;
int ans(int l, int r){
while(l < r){
int m = (r+l)>>1;
int c = sqrt(m-l+1);
vector<int> q;
for(int i = 1; i <= c; i++) q.push_back(i);
for(int i = c+l; i <= m; i += c) q.push_back(i);
if(m+1 > c) q.push_back(m+1);
if(collisions(q)) r = m;
else l = m+1;
}
vector<int> a,pr;
for(int i = 2; i*i <= l; i++){
if(l%i == 0){
a.push_back(i);
if(i*i <= l){
if(i*i != l) a.push_back(l/i);
}
}
}
sort(a.begin(), a.end());
for(int p : a){
bool cek = 1;
for(int d : pr){
if(p%d == 0){
cek = 0; break;
}
}
if(cek) pr.push_back(p);
}
int invl = -1;
while(l != invl){
invl = l;
for(auto &p : pr){
if((l/p)*p == l && collisions({1, (l/p)+1})){
l /= p; break;
}
}
}
return l;
}
signed hack(){
return ans(inf/2, inf);
}
