#include "hack.h"
#include<bits/stdc++.h>
using namespace std;
// collisions
#define get collisions
#define ll long long
#define re exit (0);
#define pb push_back
const int SKIP = 27380;
const int MAX_N = 1e9;
vector<ll> merge ( vector <ll> Left , vector<ll> Right ) {
vector<ll> res ;
for ( auto x : Left ) res . push_back (x) ;
for ( auto x : Right ) res . push_back (x) ;
return res ;
}
mt19937 rng (time(0)) ;
int hack(){
vector<ll> A,B;
for(int i = 1; i <= SKIP; i++){
A.push_back(i);
}
for(int i = SKIP * (MAX_N / 2 / SKIP); i <= MAX_N + SKIP; i += SKIP){
B.push_back(i);
}
while((int) A.size() > 1 || (int) B.size() > 1) {
if (A.size() < B.size() ) swap (A,B) ;
if(A.size() >= B.size()){
vector<ll> Al;
vector<ll> Ar;
int sz_a = A.size();
for(int i = 0; i < sz_a / 2; i++){
Al.push_back(A[i]);
}
for(int i = sz_a / 2; i < sz_a; i++){
Ar.push_back(A[i]);
}
if(get(merge(Ar, B))){
A = Ar;
} else {
A = Al;
}
}
}
int w = abs(A[0]-B[0]) ;
int x = w ;
for ( int i = 2 ; i*i <= x ; i ++ )
{
if ( x % i == 0 )
{
while ( w % i == 0 )
{
w /= i ;
if ( get ({1,1+w}) == 0 )
{
w *= i ; break ;
}
}
}
}
return w ;
}
