#include "hack.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e4 + 69;
const int inf = 1e9 + 69;
int ans;
ll collisions(vector<ll> v) ;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll n){
ll x = rng();
return abs(x) % n + 1;
}
void expiriment(int x){
vector<ll> v;
v.push_back(1);
v.push_back(1 + x);
if((collisions(v) == 1)) ans = min(ans , x);
}
int hack(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
//rand rand
vector<ll> st;
for(int i = 0;i < N; ++ i) st.push_back(rand(1e15));
vector<ll> vc;
for(auto to : st) vc.push_back(to);
//cout << collisions(vc) << ' ';
while(st.size() > 2){
vector<ll> v;
for(auto to : st){
ll x = rand(2);
if(x <= 1) v.push_back(to);
}
//cout << ' ' << collisions(v) << ' ';
if(v.size() > 1 and (collisions(v))){
st.clear();
for(auto to : v) st.push_back(to);
}
}
ll x = *st.begin() , y = *(--st.end());
ll d = abs(x - y);
//cout << d << ' ';
ans = inf;
for(ll i = 1;i * i <= d; ++ i){
if(d % i == 0){
//cout << i << ' ';
expiriment(i);
if(d / i != i and d / i <= 1e9) expiriment(d / i);
}
}
return ans;
}
