#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#include "hack.h"
using namespace std;
using ll = long long;
// n의 배수가 [l, r) 구간에 존재하는가?
bool Q(ll l, ll r)
{
ll d = r - l + 1;
ll s = 1;
while((s+1)*(s+1) <= d) s++;
vector<ll> q; q.reserve(2*s+1);
for(ll i = 1; i <= s; i++) q.push_back(i);
for(ll i = l+s; i < r; i += s) q.push_back(i);
q.push_back(r);
sort(q.begin(), q.end());
q.erase(unique(q.begin(), q.end()), q.end());
ll co = collisions(q);
// cout << format("{} {} {} {}\n", l, r, co > 0, s);
return co > 0;
}
int hack()
{
ll lo = 1e9/2;
ll hi = 1e9+1;
while(lo+1 < hi) {
ll mid = (lo+hi)/2;
if(Q(lo, mid)) hi = mid;
else lo = mid;
}
ll m = lo;
vector<ll> f;
for(ll i = 2; i*i <= m; i++) {
if(m%i == 0) f.push_back(i);
while(m%i == 0) {
m /= i;
}
}
if(m > 1) f.push_back(m);
ll n = lo;
for(auto i : f) {
while(n % i == 0) {
ll p = n / i;
if(collisions({1, p+1})) n /= i;
else break;
}
}
return n;
}
