#include "hack.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LIM = 1e9;
bool in_range(int l, int r){
int sqr = sqrt(r - l + 1);
vector<ll>p;
for(int i = 1; i <= sqr; i++){
p.push_back(i);
}
for(int i = l + sqr; i <= r; i += sqr){
p.push_back(i);
}
p.push_back(r + 1);
return collisions(p) > 0;
}
int hack(){
int low = LIM >> 1, high = LIM, ans;
while(low <= high){
int mid = (low + high) >> 1;
if(in_range(low, mid)){
high = (ans = mid) - 1;
}
else{
low = mid + 1;
}
}
vector<int>fact;
int N = ans;
for(int i = 2; i * i <= N; i++){
if(N % i == 0){
N /= i;
fact.push_back(i);
while(N % i == 0){
N /= i;
}
}
}
if(N > 1){
fact.push_back(N);
}
for(int& i : fact){
while(ans % i == 0 && collisions({1, ans / i + 1}) > 0){
ans /= i;
}
}
return ans;
}
