#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool didInit = false;
const ll MAX = 1000000;
const ll X = 9999998;
ll countt[MAX + 8] = {0};
// ll zero = 1;
vector<ll> query(X);
void init(){
// for(ll n = 2; n <= MAX; n+=2){
// zero = lcm(zero, n);
// }
for(ll n = 2; n <= MAX; n+=2){
ll h = X/(n/2);
ll c = n*h*(h-1)/4 + (h)*(X%(n/2));
countt[n] = c;
}
for(ll n = 3; n <= MAX; n+=2){
ll h = X/n;
ll c = n*h*(h-1)/2 + (h)*(X%(n));
countt[n] = c;
}
for(ll i = 0; i < X; i++){
query[i] = i*2+2;
}
didInit = true;
// cout << "zero: " << zero << '\n';
}
bool smallOrEq(ll n){
vector<ll> q;
ll nSq = sqrt(n);
for(ll x = 1; x <= nSq; x++) q.push_back(x);
for(ll x = nSq+1; x < n+1; x+=nSq) q.push_back(x);
q.push_back(n+1);
ll ans = collisions(q) > 0;
// cout << n << ": " << ans << '\n';
return ans;
}
bool soE(ll l, ll r){
vector<ll> q;
ll d = r - l + 1;
ll dSq = sqrt(d);
for(ll x = 1; x < dSq; x++){
q.push_back(x);
}
for(ll x = max(dSq, l)+1; x < r+1; x+=dSq){
q.push_back(x);
}
q.push_back(r+1);
ll ans = collisions(q) > 0;
cout << "l: " << l << " r: "<< r << "- " << ans << '\n';
return ans;
}
int hack(){
ll low = 2;
ll high = 1000000001;
while(high - low > 1){
// cout << '\n';
ll mid = low + (high - low) / 2 - 1;
// cout << "l: " << low << " h: " << high << '\n';
if(smallOrEq(mid)) high = mid + 1;
else low = mid + 1;
}
return low;
}
