Trong bài tập này nhiệm vụ của bạn là tìm số nguyên dương \(x\) tối thiểu và bạn được cung cấp một danh sách tất cả các ước của \(x\), trừ 1 và \(x\). Nếu không thể tìm được \(x\) thỏa mãn danh sách ước thì có thể coi danh sách là mâu thuẫn.

Nói cách khác, gọi \(S(x)\) là tập hợp các ước khác \(1\) và \(x\) của \(x\). Bạn được 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 là mâu thuẫn, ngược lại in ra \(x\) tối thiểu.

Example

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

48
-1