#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; 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());
// cout << format("{} {} {}\n", l, r, s);
ll co = collisions(q);
return co > 0;
}
int hack()
{
ll lo = 2;
ll hi = 1e9+1;
while(lo+1 < hi) {
ll mid = (lo+hi)/2;
if(Q(lo, mid)) hi = mid;
else lo = mid;
}
return lo;
// 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;
}
