题目描述

冰棍很喜欢高级的东西，他也觉得一些数学性质很“高级”。

冰棍有一个长为 $n$ 的序列 $\{a_i\}$。他认为如果 $a_i$ 和 $a_j$ 互质，那么 $(i,j)$ 是一个高级数对。他想知道所有高级数对中的 $i+j$ 最大是多少。

输入格式

输入第一行一个整数 $T$。

接下来 $T$ 组数据，每组第一行一个数 $n$。

接下来一行 $n$ 个空格分隔的正整数 $a_i$。

输出格式

对于每组测试数据，输出一个整数，为满足条件的最大 $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

数据范围

• 对于 $60\%$ 的数据，$n \leq 100$。
• 对于 $100\%$ 的数据，$1 \le T \leq 10$。$2 \leq n \leq 2 \cdot 10^5$，$1 \leq a_i \leq 1000$。