题目描述

给定 $n$ 个正整数 $a_1,a_2,…,a_n(1≤a_i≤1000)$的数组。找到使得 $a_i$ 和 $a_j$ 互质的 $i+j$ 的最大值；如果不存在这样的 $i,j$，输出 $-1$。

例如，考虑数组 $[1,3,5,2,4,7,7]$。由于 $a_5=4$ 和 $a_7=7$ 是互质的，因此可以获得的 $i+j$ 的最大值为 $5+7$。很显然 $a_1=1$ 与 $a_2=3$ 也互质，但 $1+2=3$ 不是最大。

如果两个整数 $p$ 和 $q$ 的最大公约数为 $1$， 则说他们是互质的。

输入格式

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

每个测试用例的第一行包含一个整数 $n(2≤n≤2⋅10^5)$ 代表数组的长度。

下一行包含 $n$ 个空格分隔的正整数 $a_1,a_2,\dots,a_n(1≤a_i≤1000)$ 代表数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，输出满足 $a_i$ 和 $a_j$ 互质的 $i+j$ 的最大值；如果没有 $i,j$ 满足条件，则输出 $-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

样例说明

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

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