#include "hack.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
#define COL collisions
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const ll MAXN = 3e5+10;
const ll MOD = 1000000;
const ll INF = 1e9;
const ll SQRT = 6500;
const ll BL = INF/SQRT+1;
ll sum(auto a, auto b){ return (a+MOD+b)%MOD; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll bisa;
ll cek(int l, int r){
if(l == r){
return COL({1, 1+l});
}
ll len = r-l;
ll sq = sqrt(len);
vector<ll> vec;
ll tot = 0, las = 1; vec.pb(1);
while(tot+sq <= len-sq){
las += sq;
vec.pb(las); // sq
tot += sq;
}
if(l!=1){
las += l; //l
vec.pb(las);
}
// for(auto in : vec ) cout << in <<' ';
// cout << " xxx\n"; cout << tot << "\n";
for(int i=1; i<=sq-1; i++){
las++;
vec.pb(las); // 1
tot++;
}
if(tot != len){
for(int i=0; i<vec.size(); i++){
if(vec[i]==1) continue;
vec[i] += len-tot;
}
vec.pb(len-tot+1);
// las += len-tot; vec.pb(las);
}
// for(auto in : vec ) cout << in <<' ';
// cout << " in\n";
return COL(vec);
}
int hack(){
int l=INF/2, r=INF, mid=0, cnt=-1;
// cout << cek(2, 2) << "pp\n";
// return 1;
while(l<=r){
// cout << l << ' ' << r <<" lr\n";
mid = md;
if(cek(l, mid)) cnt = mid, r=mid-1;
else l = mid+1, bisa = mid;
}
int X = cnt;
vector<int> coba;
for(int i=2; i*i<=cnt; i++){
if(X%i) continue;
coba.pb(i);
while(X%i == 0) X /= i;
}
if(X > 1) coba.pb(X);
for(auto in : coba){
while(cnt % in == 0 && COL({1, cnt/in + 1}) > 0)
cnt /= in;
}
if(cnt==-1) assert(false);
return cnt;
}
// jwbn sample 5, 2
