Gọi \(S(x)\) là tập hợp các ước khác \(1\) và \(x\) của \(x\). Cho tập \(D\), hãy tìm số \(x\) nhỏ nhất có \(S(x) = D\) là tập đã cho.

Input

• Dòng đầu tiên chứa số \(T\) \((T \leq 25)\) là số lượng truy vấn. Sau đó \(T\) dòng tiếp theo.
  • Dòng đầu tiên của mỗi truy vấn chứa số nguyên \(n\) \((n \leq 300)\) là số lượng của danh sách.
  • Dòng thứ hai của mỗi truy vấn chứa \(n\) số nguyên \(d_1, d_2, ... d_n\), với \(d_i\) \((d_i \leq 10^6)\) là một trong những ước của số đang đoán và tất cả \(d_i\) là khác biệt. Nói cách khác \(D = \{d_1, d_2, ..., d_n\}\)

Output

• Gồm \(T\) dòng mỗi dòng in ra \(-1\) nếu danh sách đó không thỏa mãn \(x\) nào, ngược lại in ra \(x\) tối thiểu.

Ví dụ:

Input

2
8
8 2 12 6 4 24 16 3
2
4 7

Output

48
-1

Giải thích:

• \(S(48) = \{2, 3, 4, 6, 8, 12, 16, 24\}\) là các ước khác \(1\) và \(48\) của \(48\).

Ràng buộc

• Subtask \(1\) (\(30\%\) số điểm): \(|s| \leq 10\);
• Subtask \(2\) (\(30\%\) số điểm): \(|s| \leq 1000\);
• Subtask \(3\) (\(40\%\) số điểm): \(|s| \leq 5 * 10^5\).