#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 calc(ll x, ll y)
{
if (x > y)
swap(x, y);
ll tam = y - x, i;
vector<ll> divs;
for (i = 2; i <= sqrt(tam); i++)
{
if (tam % i != 0)
continue;
if (collisions({1 + i, 1}))
return i;
if (i != sqrt(tam))
divs.pb(tam / i);
}
while (sz(divs))
{
if (collisions({divs.back() + 1, 1}))
return divs.back();
divs.pop_back();
}
return tam;
}
const ll maxM = 1e9, prim = 14009;
// const ll maxM=1e1, prim=3;
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 calc(v[0], u[0]);
}
