#include <bits/stdc++.h>
using namespace std;
long long collisions(std::vector<long long> x);
using ll = long long;
int hack() {
ll m = 31623;
if (m == 1) return 1;
ll l = 1, h = m;
while (l < h) {
ll mid = (l + h) / 2;
vector<long long> vec;
for (ll i = 0; i < m; i++) vec.push_back(i + 1);
for (long long i = l; i <= mid; i++) {
vec.push_back(i * m + 1);
}
if (collisions(vec)) {
h = mid;
} else {
l = mid + 1;
}
}
ll q = l;
l = 0, h = m - 1;
while (l < h) {
ll mid = (l + h) / 2;
vector<long long> vec = {q * m + 1};
for (ll i = l; i <= mid; i++) {
vec.push_back(i + 1);
}
if (collisions(vec)) {
h = mid;
} else {
l = mid + 1;
}
}
return q * m - l;
}
