#include <algorithm> #include <bitset> #include <iostream> #include <unordered_map> #include <vector> using namespace std; using i64 = long long; int n; vector<int> a; i64 gcd(i64 x, i64 y) { if (x == 0 || y == 0) return x | y; const int i = __builtin_ctz(x); x >>= i; const int j = __builtin_ctz(y); y >>= j; const int k = i < j ? i : j; // min(i, j) while (true) { if (x > y) { i64 t = x; x = y; y = t; } y -= x; if (y == 0) return x << k; y >>= __builtin_ctz(y); } } inline i64 lcm(i64 x, i64 y) { return x == 0 ? y : x / gcd(x, y) * y; } struct Solver1 { static constexpr int N = 1e3; void main() { bitset<N * N + 2> vis(1); for (int i = 0; i < n; ++i) { int cur = 0; for (int j = i; j < n; ++j) { i64 nxt = lcm(cur, a[j]); if (nxt > n * n + 1) break; cur = nxt; vis[cur] = true; } } cout << (~vis)._Find_first() << '\n'; } }; struct Solver2 { static constexpr int LIM = 1 << 30, JMP = 17; int* table[JMP]; ~Solver2() { for (auto row : table) delete[] row; } int lcm(int x, int y) { if (x == -1 || y == -1) return -1; i64 res = ::lcm(x, y); return res >= LIM ? -1 : res; } int query(int l, int r) { int jmp = __lg(r - l + 1); return lcm(table[jmp][l], table[jmp][r - (1 << jmp) + 1]); } void main() { for (int i = 0; i < JMP; ++i) table[i] = new int[n]; copy(a.begin(), a.end(), table[0]); for (int i = 1; i < JMP; ++i) { for (int j = 0; j + (1 << i) < n; ++j) table[i][j] = lcm(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); } unordered_map<int, bool> vis; for (int i = 0; i < n; ++i) { int j = i - 1, lst = 0; while (j < n && lst != -1) { if (j + 1 >= n) break; int l = j + 1, r = n - 1; while (l < r) { int mid = (l + r) >> 1; if (query(i, mid) != lst) r = mid; else l = mid + 1; } lst = query(i, j = l); vis[lst] = true; } } for (int i = 1;; ++i) { if (!vis[i]) { cout << i << '\n'; break; } } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T; while (T-- > 0) { cin >> n; bool have_1 = false; a.resize(n); for (int& x : a) { cin >> x; if (x == 1) have_1 = true; } if (!have_1) { cout << "1\n"; continue; } if (n <= 1000) Solver1().main(); else Solver2().main(); } return 0; }