#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1
const int maxn = 1e6;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
// static int n = 0;
// static int total_cost = 0;
// long long collisions(std::vector<long long> x){
// total_cost += (int) x.size();
// if (total_cost > 1000000){
// printf("Total cost exceeded 1,000,000\n");
// exit(0);
// }
// long long res = 0;
// std::map<int, int> table;
// std::set<long long> seen;
// for (long long v : x){
// if (v < 1 || v > (long long)1e18){
// printf("x[i] is out of range\n");
// exit(0);
// }
// if (seen.find(v) != seen.end()){
// printf("x has a duplicate element\n");
// exit(0);
// }
// seen.insert(v);
// res += table[v % n];
// table[v % n]++;
// }
// return res;
// }
int hack(){
// std::vector<long long> x = {1, 2, 3};
// long long a = collisions(x);
// long long b = collisions({92, 65});
// return 42;
int ans = 0;
vector<ll> v;
for (int i = 1; i <= maxn; i++) {
v.pb(i);
}
ll a = collisions(v);
for (int i = 1; i <= maxn; i++) {
int x = maxn / i;
int y = maxn % i;
ll sum = (ll)x * (x - 1) * i / 2 + x * y;
if (sum == a) {
ans = i;
break;
}
}
return ans;
// while (l < r) {
// cout << l << ' ' << r << '\n';
// int m = (l + r) / 2;
// int x = maxn / m;
// int y = maxn % m;
// int sum = x * (x - 1) * m / 2 + x * y;
// if (sum == a) {
// l = r = m; break;
// }
// else if (sum < a) {
// r = m - 1;
// } else l = m + 1;
// }
// return l;
}
// int main(){
// int t;
// assert(1 == scanf("%d", &t));
// std::vector<int> ns(t);
// for (int i = 0; i < t; i++){
// assert(1 == scanf("%d", &ns[i]));
// }
// for (int i = 0; i < t; i++){
// total_cost = 0;
// n = ns[i];
// int ans = hack();
// printf("%d %d\n", ans, total_cost);
// }
// return 0;
// }
