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.

题目大意：
给定一个长度为 \( n \)（\( 2 \le n \le 2 \times 10^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 \) 互质。

输入输出数据格式：
输入格式：
- 输入包含多个测试用例。第一行包含一个整数 \( t \)（\( 1 \leq t \leq 10 \)）——测试用例的数量。接下来是每个测试用例的描述。
- 每个测试用例的第一行包含一个整数 \( n \)（\( 2 \leq n \leq 2 \times 10^5 \)）——数组的长度。
- 下一行包含 \( n \) 个空格分隔的正整数 \( a_1, a_2, \dots, a_n \)（\( 1 \leq a_i \leq 1000 \)）——数组的元素。
- 保证所有测试用例的 \( n \) 之和不超过 \( 2 \times 10^5 \)。

输出格式：
- 对于每个测试用例，输出一个整数——满足 \( a_i \) 和 \( a_j \) 互质的 \( i+j \) 的最大值，如果不存在这样的 \( i,j \)，则输出 \( -1 \)。

输入输出样例：
输入样例 #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
```题目大意： 给定一个长度为 \( n \)（\( 2 \le n \le 2 \times 10^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 \) 互质。 输入输出数据格式： 输入格式： - 输入包含多个测试用例。第一行包含一个整数 \( t \)（\( 1 \leq t \leq 10 \)）——测试用例的数量。接下来是每个测试用例的描述。 - 每个测试用例的第一行包含一个整数 \( n \)（\( 2 \leq n \leq 2 \times 10^5 \)）——数组的长度。 - 下一行包含 \( n \) 个空格分隔的正整数 \( a_1, a_2, \dots, a_n \)（\( 1 \leq a_i \leq 1000 \)）——数组的元素。 - 保证所有测试用例的 \( n \) 之和不超过 \( 2 \times 10^5 \)。 输出格式： - 对于每个测试用例，输出一个整数——满足 \( a_i \) 和 \( a_j \) 互质的 \( i+j \) 的最大值，如果不存在这样的 \( i,j \)，则输出 \( -1 \)。 输入输出样例： 输入样例 #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 ```