← 返回比赛

已结束 GESP欢乐赛 #5

← 上一题下一题 →

A1441 | $互质$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个由 $n$ 个正整数 $a_1$ ~ $a_n$ 组成的数组 $a$，找到最大的 $i+j$ ，并且满足 $a_i$ 和 $a_j$ 互质，如果不存在这样的 $i$、$j$，打印 -1 。

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 10$)。 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^5$) — 表示数组的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1$~$a_n$ （$0 \le a_i \le 1000$）。

输出格式

对于每个测试用例，输出一个整数 — 找到最大的 $i+j$ ，并且满足 $a_i$ 和 $a_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

C++ 编辑器

输入

输出