← 返回题目列表

Codeforces · 1834/E

E. LCM 的 MEX

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$。如果无法找到数组的子段$$$^{\dagger}$$$ 使得其所有元素的最小公倍数等于$$$x$$$,则正整数$$$x$$$ 被称为好整数。

您需要找到最小的好整数。

数组 $$$a$$$ 的子段 $$$^{\dagger}$$$ 是一组元素 $$$a_l, a_{l + 1}, \ldots, a_r$$$ 对于某些 $$$1 \le l \le r \le n$$$。我们将这样的子段表示为$$$[l,r]$$$。

输入

每个测试由多个测试用例组成。每个测试用例的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 最小的好整数。

示例

输入 #1

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

输出 #1

4
7
1
1
16
13

注意

在第一个测试用例中,$$$4$$$ 是一个好的整数,而且它是最小的整数,因为整数 $$$1,2,3$$$ 出现在数组中,这意味着长度为 $$$1$$$ 的数组存在具有 $$$1,2,3$$$ 最小公倍数的子段。然而,不可能找到最小公倍数等于$$$4$$$的数组子段。

在第二个测试用例中,$$$7$$$ 是一个很好的整数。整数 $$$1,2,3,4,5$$$ 明确出现在数组中,整数 $$$6$$$ 是子段 $$$[2, 3]$$$ 和 $$$[1, 3]$$$ 的最小公倍数。

在第三个测试用例中,$$$1$$$ 是一个好的整数,因为子段 $$$[1, 1]、[1, 2]、[2, 2]$$$ 中整数的最小公倍数分别为 $$$2,6,3$$$。