CF1742D Coprime

给定一个包含 $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$ 是[互质数](https://en.wikipedia.org/wiki/Coprime_integers)，当且仅当它们的[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)为 $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 翻译