Coprime

题意翻译

给定一个长为 $n\ (2\le n\le 2\times10^5)$ 的序列 $a\ (1\le a_i\le 1000)$，求 $\max\limits_{\gcd(a_i,a_j)=1}\{i+j\}$。换句话说，求 $i+j$ 的最大值，其中 $i,j$ 满足 $a_i$ 和 $a_j$ 互质。

题目描述

Given an array of $ n $ positive integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 1000 $ ). Find the maximum value of $ i + j $ such that $ a_i $ and $ a_j $ are coprime, $ ^{\dagger} $ or $ -1 $ if no such $ i $ , $ j $ exist. For example consider the array $ [1, 3, 5, 2, 4, 7, 7] $ . The maximum value of $ i + j $ that can be obtained is $ 5 + 7 $ , since $ a_5 = 4 $ and $ a_7 = 7 $ are coprime. $ ^{\dagger} $ Two integers $ p $ and $ q $ are [coprime](https://en.wikipedia.org/wiki/Coprime_integers) if the only positive integer that is a divisor of both of them is $ 1 $ (that is, their [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) is $ 1 $ ).

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2\cdot10^5 $ ) — the length of the array. The following line contains $ n $ space-separated positive integers $ a_1 $ , $ a_2 $ ,..., $ a_n $ ( $ 1 \leq a_i \leq 1000 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case, output a single integer — the maximum value of $ i + j $ such that $ i $ and $ j $ satisfy the condition that $ a_i $ and $ a_j $ are coprime, or output $ -1 $ in case no $ i $ , $ j $ satisfy the condition.

输入输出样例

输入样例 #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

说明

For the first test case, we can choose $ i = j = 3 $ , with sum of indices equal to $ 6 $ , since $ 1 $ and $ 1 $ are coprime. For the second test case, we can choose $ i = 7 $ and $ j = 5 $ , with sum of indices equal to $ 7 + 5 = 12 $ , since $ 7 $ and $ 4 $ are coprime.