#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])); }