(24-25赛季)稠州常规赛23

P5. 幽默数（humor）

描述

给定一个长度为 $n$ 的正整数序列 $a$ 。一个正整数 $x$ 被称为「幽默的」，当且仅当不存在一个子区间，使得其所有元素的最小公倍数等于 $x$ 。

你需要找到最小的「幽默的」数。

序列 $a$ 的子区间指的是序列中的一组元素 $a_l,a_{l+1},\cdots,a_r$ ，其中 $1\leq l\leq r\leq n$ 。我们将这样的子区间表示为 $[l,r]$ 。

输入

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

对于每组数据，第一行一个整数 $n$ ，第二行 $n$ 个整数 $a_{1\sim n}$ 。

输出

对于每组数据，输出一行一个整数表示答案。

样例

6
3
1 2 3
5
1 2 3 4 5
2
2 3
1
1000000000
12
1 8 4 2 3 5 7 2 9 10 11 13
12
7 2 5 4 2 1 1 2 3 11 8 9

提示

在第一组样例数据中， $4$ 是一个幽默数，并且是最小的，因为数组中出现了整数 $1,2,3$ ，这意味着存在长度为 $1$ 的子区间，其最小公倍数分别为 $1,2,3$ ，并且不存在最小公倍数等于 $4$ 的子区间。

在第二组样例数据中， $7$ 是一个幽默数，整数 $1\sim 5$ 明确出现在数组中，而整数 $6$ 是子区间 $[2,3]$ 和 $[1,3]$ 的最小公倍数。

在第三组样例数据中， $1$ 是一个幽默数，因为子区间 $[1,1],[1,2],[2,2]$ 的最小公倍数分别为 $2,6,3$ 。

对于 $20\%$ 的数据， $1\leq n\leq 100$ 。

对于 $40\%$ 的数据， $1\leq n\leq 1000$ 。

对于另外 $30\%$ 的数据， $1\leq a_i\leq 10^5$ 。

对于 $100\%$ 的数据， $1\leq T\leq 10$ ， $1\leq n\leq 10^5$ ， $1\leq a_i\leq 10^9$ 。

提交

题目参数

时间限制	1 秒
内存限制	256 MB