//chockolateman
#include<bits/stdc++.h>
#include <vector>
#include "hack.h"
using namespace std;
map<vector<long long>,bool> done;
map<vector<long long>,long long> memo;
vector<int> nums;
long long query(vector<long long> &temp)
{
if(done[temp])
return memo[temp];
done[temp] = true;
memo[temp] = collisions(temp);
return memo[temp];
}
int hack(){
done.clear();
memo.clear();
std::vector<long long> temp;
bool broke = false;
int counter = -1;
if(nums.empty())
for(int i = 1 ; i <= 1000000 ; i++)
nums.push_back(i);
random_shuffle(nums.begin(),nums.end());
while(!broke)
{
temp.clear();
counter++;
temp.push_back(1);
temp.push_back(1 + nums[counter]);
if(query(temp))
broke = true;
}
int n = nums[counter];
for(int x = 1 ; x <= n ; x++)
if(n%x==0)
{
temp.clear();
temp.push_back(1);
temp.push_back(1 + x);
if(query(temp))
n = x;
}
return n;
}
