#include <algorithm> #include <bitset> #include <iostream> #include <vector> using namespace std; using i64 = long long; int n; vector<int> a; i64 gcd(i64 x, i64 y) { while (y != 0) { i64 t = x % y; x = y; y = t; } return x; } inline i64 lcm(i64 x, i64 y) { if (x == 0) return y; else if (y == 0) return x; else return x * y / gcd(x, 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; vector<int> table[JMP]; 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() { table[0] = a; for (int i = 1; i < JMP; ++i) { table[i].resize(n); for (int j = 0; j + (1 << i) < n; ++j) table[i][j] = lcm(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); } vector<int> 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; } int now = query(i, l); if (now == lst) break; j = l; lst = now; if (lst != -1) vis.push_back(lst); } } sort(vis.begin(), vis.end()); int lst = 0; for (int x : vis) { if (x - lst > 1) { cout << lst + 1 << '\n'; return; } lst = x; } cout << lst + 1 << '\n'; } }; 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; }