#include <bits/stdc++.h>
#include "hack.h"
#define int long long
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
/*
10
67
31912
5131
53187
674319
13
17
3
351728
431
*/
vi fact[1000001];
int can[1000001];
void pre() {
for (int f = 2; f <= 1e6; f++) {
for (int mul = 2*f; mul <= 1e6; mul += f) {
fact[mul].pb(f);
}
}
for (int i = 1; i <= 1e6; i++) fact[i].pb(i);
}
bool done = false;
signed hack() {
if (!done) {
pre();
done = true;
}
memset(can, 0, sizeof(can));
int lim = 1e6 + 1;
for (int it = lim; it >= 2; it--) {
if (can[it - 1] == -1) continue;
vi x = {1, it};
int y = collisions(x);
if (y > 0) {
// cout << 1 << " " << it << " matched\n";
int ptr = it - 1;
vi facts = fact[ptr];
sort(all(facts));
for (auto &fac : facts) {
int f = fac;
if (f == 1) continue;
if (can[f] == -1) continue;
else {
// maybe change
vi y = {1, f + 1};
if (collisions(y) > 0) {
return f;
}
}
}
} else {
int ptr = it - 1;
for (auto &f : fact[ptr]) {
can[f] = -1;
can[ptr / f] = -1;
}
}
}
assert(false);
return 10;
}
