题目描述

给定一个包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 的数组（$1 \le a_i \le 1000$）。请你找出最大的 $i + j$，使得 $a_i$ 和 $a_j$ 互质$^{\dagger}$，如果不存在这样的 $i, j$，输出 $-1$。

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

$^{\dagger}$ 两个整数 $p$ 和 $q$ 是互质数，当且仅当它们的最大公约数为 $1$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10$）——表示测试数据的组数。每组测试数据描述如下：

每组的第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot10^5$）——数组的长度。

接下来一行包含 $n$ 个用空格分隔的正整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 1000$）——数组的元素。

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

输出格式

对于每组测试数据，输出一个整数——满足条件的最大 $i + j$，如果不存在满足条件的 $i, j$，则输出 $-1$。

说明/提示

对于第一个测试用例，可以选择 $i = j = 3$，此时下标之和为 $6$，因为 $1$ 和 $1$ 互质。

对于第二个测试用例，可以选择 $i = 7$ 和 $j = 5$，下标之和为 $7 + 5 = 12$，因为 $7$ 和 $4$ 互质。

由 ChatGPT 4.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

6
12
9
-1
10
7