#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll B = 22303;
const ll N = 1e9;
inline bool q(vector<ll> a, const vector<ll>& b){
a.insert(a.end(), b.begin(), b.end());
return collisions(a) > 0;
}
int hack(){
vector<ll> a, b;
for(ll i=1;i<=B;i++) a.push_back(i);
for(ll x=((N/2)/B)*B;x<=N+B;x+=B) b.push_back(x);
while(a.size()>1 || b.size()>1){
if(a.size()<=b.size()) swap(a,b);
int m=a.size()/2;
vector<ll> l(a.begin(),a.begin()+m), r(a.begin()+m,a.end());
a = q(l,b) ? l : r;
}
ll x = llabs(a[0]-b[0]), t=x;
for(ll p=2;p*p<=t;p++){
while(t%p==0){
if(collisions({1,x/p+1})) x/=p;
t/=p;
}
}
if(t>1 && collisions({1,x/t+1})) x/=t;
return x;
}
