#include <bits/stdc++.h>
using namespace std;
using l = long long;
int collisions(vector<l>);
#define cl collisions
const int S = 26767;
const int M = 1e9;
vector<int> f(int x){
vector<int> r;
for(int i=2;i*i<=x;i++){
while(x%i==0){
r.push_back(i);
x/=i;
}
}
if(x>1) r.push_back(x);
return r;
}
int hack(){
vector<l> a,b;
for(int i=1;i<=S;i++) a.push_back(i);
for(int i=S*(M/2/S);i<=M+S;i+=S) b.push_back(i);
while(a.size()>1||b.size()>1){
if(a.size()>b.size()){
int n=a.size();
vector<l> x(a.begin(),a.begin()+n/2),y(a.begin()+n/2,a.end());
vector<l> t=y;
t.insert(t.end(),b.begin(),b.end());
if(cl(t)) a=y;
else a=x;
}else{
int n=b.size();
vector<l> x(b.begin(),b.begin()+n/2),y(b.begin()+n/2,b.end());
vector<l> t=a;
t.insert(t.end(),x.begin(),x.end());
if(cl(t)) b=x;
else b=y;
}
}
int u=a[0],v=b[0];
int d=v-u;
for(int p:f(d)){
d/=p;
if(cl({1,(l)d+1})==0) d*=p;
}
return d;
}
