#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz size()
using namespace std;
ll collisions(vector<ll> x);
bool ask(const vector<ll>& v, const vector<ll>& u){
vector<ll> q;
q.reserve(v.sz+u.sz);
for(auto i:v){q.pb(i);}
for(auto i:u){q.pb(i);}
ll k = collisions(q);
return k>0;
}
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 && cand>=2 && 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;
}
int hack(){
ll mx=(ll)(1e9);
const int b = 10007;
vector<ll> v,u;
for(int i = 1; i <= b; i++){
v.pb(i);
}
for(ll x = ((mx>>1)/b)*b; x <= mx+b; x+=b){
u.push_back(x);
}
while(v.sz > 1 || u.sz > 1){
if(v.sz < u.sz){
swap(v,u);
}
int mid=(v.sz>>1);
vector<ll> l(v.begin(),v.begin()+mid);
vector<ll> r(v.begin()+mid,v.end());
if(ask(l,u)){
v.swap(l);
}else{
v.swap(r);
}
}
//return llabs(v[0]-u[0]); -> es multiplo pero no necesariamente n
return solve(llabs(v[0]-u[0]));
}
