← 返回题目列表

Codeforces · 1742/D

D. 共质

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

给定 $$$n$$$ 正整数数组 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$)。求 $$$i + j$$$ 的最大值,使得 $$$a_i$$$ 和 $$$a_j$$$ 互质,$$$^{\dagger}$$$ 或 $$$-1$$$(如果不存在这样的 $$$i$$$、$$$j$$$ )。

例如,考虑数组 $$$[1, 3, 5, 2, 4, 7, 7]$$$。可获得的 $$$i + j$$$ 的最大值为 $$$5 + 7$$$,因为 $$$a_5 = 4$$$ 和 $$$a_7 = 7$$$ 互质。

$$$^{\dagger}$$$ 如果作为两个整数 $$$p$$$ 和 $$$q$$$ 的约数的唯一正整数是 $$$1$$$(即它们的最大公约数是 $$$1$$$),则这两个整数是互质的。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — 数组的长度。

以下行包含 $$$n$$$ 以空格分隔的正整数 $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$1 \leq a_i \leq 1000$$$) - 数组的元素。

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

输出

对于每个测试用例,输出一个整数 - $$$i + j$$$ 的最大值,使得 $$$i$$$ 和 $$$j$$$ 满足 $$$a_i$$$ 和 $$$a_j$$$ 互质的条件,或者在 $$$i$$$、$$$j$$$ 不满足条件的情况下输出 $$$-1$$$。

示例

输入 #1

6
3
3 2 1
7
1 3 5 2 4 7 7
5
1 2 3 4 5
3
2 2 4
6
5 4 3 15 12 16
5
1 2 2 3 6

输出 #1

6
12
9
-1
10
7

注意

对于第一个测试用例,我们可以选择 $$$i = j = 3$$$,索引之和等于 $$$6$$$,因为 $$$1$$$ 和 $$$1$$$ 是互质的。

对于第二个测试用例,我们可以选择 $$$i = 7$$$ 和 $$$j = 5$$$,索引之和等于 $$$7 + 5 = 12$$$,因为 $$$7$$$ 和 $$$4$$$ 是互质的。