Cho dãy số nguyên dương ~a~ gồm ~n~ phần tử.

Ta gọi ~V~ là tích tất cả các phần tử của dãy ~a~.

Hãy tìm số nguyên dương ~x~ nhỏ nhất, sao cho ~V~ không chia hết cho ~x~.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 10^5~) là số bộ tests. Mỗi bộ test gồm:

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 10^5~) - số phần tử của dãy.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~1 \le a_i \le 10^5~) - các phần tử của dãy.

Dữ liệu đảm bảo ~\sum n \le 10^5~.

Output

Với mỗi test, in ra số nguyên dương ~x~ nhỏ nhất, sao cho ~V~ không chia hết cho ~x~.

Lưu ý, kết quả có thể vượt quá ~10^{18}~.

Sample Input 1

2
5
4 3 2 4 6
4
2 10 14 4

Sample Output 1

5
3

Trong test 1, ~5~ là số nhỏ nhất mà ~576~ không chia hết.