#include "hack.h"
#include <bits/stdc++.h>
#define REP(i,a,b) for(long long i = a; i<b; i++)
#define RREP(i,a,b) for(int i = a; i>b; i--)
typedef long long ll;
using namespace std;
bool check(int l, int r){
ll s = sqrt(r-l+1);
vector<ll> v(0);
v.push_back(r);
REP(i,1,s+1){
v.push_back(i);
}
for(ll i = l+s; i<r; i+=s){
v.push_back(i);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
ll x = collisions(v);
return x>0;
}
ll search(ll lo, ll hi){
if(lo == hi){
vector<ll> fact;
ll m = lo;
REP(i,2,sqrt(lo)+1){
if(m%i == 0){
fact.push_back(i);
while(m%i== 0){
m/=i;
}
}
}
if(m!=1) fact.push_back(m);
ll n = lo;
for(ll i: fact){
while(n%i == 0){
ll tmp = n/i;
if(collisions({1, tmp+1})>0) n/=i;
else{
break;
}
}
}
return n;
}
ll mid = (lo+hi)/2;
if(check(lo, mid+1)){
return search(lo, mid);
}
return search(mid+1, hi);
}
int hack(){
return search(2,1e9);
}
