题目描述

Alice 有一个长为 $n$ 的序列 $\{a_i\}$，她想用这个序列出一些题考 Bob。具体而言，她想考考 Bob 能不能把一些正整数写成 $\{a_i\}$ 里的非空子序列的 LCM。例如，如果 $\{a_i\} = [2,4,6,7,8]$，那么 $24$ 可以写成 $\operatorname{lcm}(6, 8)$，$84$ 可以写成 $\operatorname{lcm}(4,6,7)$。

Alice 想在里面塞一道无解的题来坑害 Bob，但是她希望这个数尽可能的小，以便混淆视听。例如在上述序列里，$11$ 和 $48$ 都不能写成非空子序列的 LCM，但是最小的这样的数是 $1$。换言之，她想找到最小的正整数 $x$，使得不存在一个非空子序列的 LCM 等于 $x$。

Alice 发现自己求不出这个数，所以希望你帮帮她。

输入格式

第一行一个整数 $T$ 表示询问组数。

接下来 $T$ 组询问：

每组询问第一行一个整数 $n$，代表序列的长度。

接下来一行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

输出格式

共 $T$ 行，每行一个整数，代表该组询问的答案。

3
5
2 4 6 7 8
5
1 2 3 4 5
4
1 2 3 5

1
7
4

数据范围

对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 500$； 对于另外 $30\%$ 的数据，$1 \le a_i \le 10^5$； 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$，$1 \le \sum n \le 10^5$。