#include "hack.h"
#include<bits/stdc++.h>
using namespace std;
// collisions
#define get collisions
#define ll long long
#define re exit (0);
const int p = 27512 , q = 18175 , M = 5e8 ;
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 ;
}
int hack(){
vector<ll> A ;
for ( int i = 1 ; i <= p ; i ++ ) A . push_back (i) ;
for ( int i = 1 ; i <= q ; i ++ ) A . push_back (M+i*p) ;
int x ;
while ( A.size () > 2 )
{
vector <ll> Left , Right1 , Right2 ;
for ( int i = 0 ; i < A.size()/2 ; i ++ ) Left . push_back (A[i]) ;
for ( int i = A.size()/2 ; i < A.size()/2 + A.size()/4 ; i ++ ) Right1 . push_back (A[i]) ;
for ( int i = A.size()/2 + A.size()/4 ; i < A.size () ; i ++ ) Right2 . push_back (A[i]) ;
if ( get (merge(Left,Right1)) ) A = merge (Left,Right1) ;
else A = merge (Left,Right2) ;
if ( A.size () == 2 )
{
x = abs (A[0]-A[1]) ; break ;
}
if ( A.size () == 3 )
{
if ( get ({A[0],A[1]})) x = abs (A[0]-A[1]) ;
else if ( get ({A[0],A[2]})) x = abs (A[0]-A[2]) ;
else x = abs (A[1]-A[2]) ;
break ;
}
}
int w = x ;
for ( int i = 2 ; i*i <= x ; i ++ )
{
if ( x % i == 0 )
{
while ( true )
{
w /= i ;
if ( get ({1,1+w}) == 0 )
{
w *= i ; break ;
}
x /= i ;
}
}
}
return w ;
}
