#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
*/
signed hack() {
mii can;
int i = 1e6;
for (int it = i; it >= 2; it--) {
if (can[it] == -1) continue;
vi x = {1, it};
int y = collisions(x);
if (y > 0) {
int ptr = it - 1;
// cout << "1 " << ptr << " gives a match\n";
vi facts;
for (int f = 1; f * f <= ptr; f++) {
if ((ptr % f) != 0) continue;
facts.pb(f); facts.pb(ptr/f);
}
sort(all(facts));
// for (auto &fac : facts) cout << fac << " ";
// cout << '\n';
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 (int f = 2; f * f <= ptr; f++) {
if ((ptr % f) != 0) continue;
can[f] = -1;
can[ptr / f] = -1;
}
}
}
return 10;
}
