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