#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define fr first
#define se second
#define pb push_back
using namespace std;
long long collisions(std::vector<long long> x);
bool can(vector<ll> v, vector<ll> u)
{
map<ll, ll> used;
for (auto k : v)
used[k] = 1;
for (auto k : u)
if (used[k])
continue;
else
{
used[k] = 1;
v.pb(k);
}
return collisions(v);
}
ll solve(ll x) {
ll n=x, di=x;
for(ll p=2; p*p <= di; p++){
while(di%p==0){
ll cand=n/p;
if(n%p==0 && collisions({1, cand+1})>0){
n/=p;
}
di/=p;
}
}
ll cand=n/di;
if(n%di==0 && di>1){
if(collisions({1,cand+1}) > 0)
n=cand;
}
return n;
}
const ll maxM = 1e9, prim = 14009;
int hack()
{
ll i, j;
vector<ll> v(prim), u;
iota(v.begin(), v.end(), 1);
for (i = ((maxM / 2) / prim) * prim; i <= maxM + prim; i += prim)
u.pb(i);
while (sz(v) > 1 || sz(u) > 1)
{
if (sz(v) < sz(u))
swap(v, u);
ll mid = sz(v) / 2;
if (can(vector(v.begin() + mid, v.end()), u))
v = vector(v.begin() + mid, v.end());
else
v.resize(mid);
}
return solve(abs(v[0]-u[0]));
}
