#include "hack.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const ll N=1e6,mod=1e9+7,sq=27383;
ll coll(vector<ll>a,vector<ll>b){
vector<ll>v;
for(auto i:a)
v.push_back(i);
for(auto i:b)
v.push_back(i);
return collisions(v);
}
int hack(){
vector<ll> a,b;
for(int i=1;i<=sq;i++)
a.push_back(i);
for(int i=sq*(5e8/sq);i<=1e9+sq;i+=sq)
b.push_back(i);
while(a.size()>1 || b.size()>1){
if(a.size()>b.size()){
vector<ll>f,s;
int idx;
//cout<<"F: ";
for(idx=0;idx<a.size()/2;idx++){
f.push_back(a[idx]);
//cout<<a[idx]<<" ";
}
//cout<<endl<<"S: ";
for(;idx<a.size();idx++){
s.push_back(a[idx]);
//cout<<a[idx]<<" ";
}
//cout<<endl;
if(coll(s,b))
a=s;
else
a=f;
}
else{
vector<ll>f,s;
int idx;
//cout<<"F: ";
for(idx=0;idx<b.size()/2;idx++){
f.push_back(b[idx]);
//cout<<b[idx]<<" ";
}
//cout<<endl<<"S: ";
for(;idx<b.size();idx++){
s.push_back(b[idx]);
//cout<<b[idx]<<" ";
}
//cout<<endl;
if(coll(a,f))
b=f;
else
b=s;
}
}
//cout<<a[0]<<" "<<b[0]<<endl;
//cout<<coll(a,b);
ll m=b[0]-a[0],m1=m;
set<int>prime;
for (int i=2;i*i<=1e9;i++){
while(m1%i==0){
m1/=i;
prime.insert(i);
}
}
if(m1!=1)
prime.insert(m1);
for(auto i:prime){
while(m%i==0 && collisions({1,m/i+1})){
m/=i;
}
}
return m;
}
