#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 = l+(r-l)/2;
int c = sqrtl(m-l+1);
vector<int> q;
for(int i = 1; i <= c; i++) q.push_back(i);
for(int i = c+1; 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<bool> cek(l+7,1);
vector<int> a;
cek[0] = cek[1] = 0;
for(int i = 2; i*i <= l; i++){
if(cek[i]){
a.push_back(i);
for(int j = i*i; j*j <= l; j+= i) cek[j] = 0;
}
}
int invl = -1;
while(l != invl){
invl = l;
for(auto &p : a){
if((l/p)*p == l && collisions({1, (l/p)+1})){
l /= p; break;
}
}
}
return l;
}
signed hack(){
return ans(inf/2, inf);
}
