#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll collisions(vector<ll> x);
const int T = 500;
int hack() {
vector<ll> group;
for (int i = 1; i <= T; i++)
group.push_back(i);
for (int i = 1; i <= T; i++)
group.push_back(T + T * i);
if (collisions(group)) {
int l = 1, r = (int)(1e6);
while (l < r) {
int mid = (l + r) / 2;
int S = sqrt(mid - l + 1);
vector<ll> pts;
for (int i = 1; i <= S; i++)
pts.push_back(i);
for (int i = mid + 1; i > max(l, S); i -= S)
pts.push_back(i);
if (collisions(pts)) r = mid;
else l = mid + 1;
}
return l;
}
int l = (int)(4.95e8), r = (int)(1e9);
while (l < r) {
int mid = (l + r) / 2;
int S = sqrt(mid - l + 1);
vector<ll> pts;
for (int i = 1; i <= S; i++)
pts.push_back(i);
for (int i = mid + 1; i > max(l, S); i -= S)
pts.push_back(i);
if (collisions(pts)) r = mid;
else l = mid + 1;
}
vector<int> ff;
int t = l;
for (int d = 2; d * d <= t; d++)
while (t % d == 0) {
ff.push_back(d);
t /= d;
}
if (t > 1)
ff.push_back(t);
int ans = l;
if (!ff.empty()) {
for (int x : ff)
if (collisions({1, 1 + ans / x}))
ans /= x;
}
return ans;
}
