Дан массив из \(n\) целых положительных чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 1000\)). Выведите максимальное значение \(i + j\) такое, что \(a_i\) и \(a_j\) взаимно простые\(^{\dagger}\), или \(-1\), если таких \(i\) и \(j\) не существует.
Например, рассмотрим массив \([1, 3, 5, 2, 4, 7, 7]\). Максимальное значение \(i + j\), которое можно получить, равно \(5 + 7\), так как \(a_5 = 4\) и \(a_7 = 7\) являются взаимно простые.
\(^{\dagger}\) Два целых числа \(p\) и \(q\) являются взаимно простыми, если единственное положительное целое число, которое является делителем их обоих, равно \(1\) (их наибольший общий делитель равен \(1\)).
Выходные данные
Для каждого набора выведите одно целое число — максимальное значение \(i + j\), такое, что \(i\) и \(j\) удовлетворяют условию, что \(a_i\) и \(a_j\) взаимно просты, или выведите \(-1\), если не существует таких \(i\) и \(j\).
Примечание
Для первого примера можно выбрать \(i = j = 3\), при этом сумма индексов равна \(6\), так как \(1\) и \(1\) - взаимно простые.
Для второго примера можно выбрать \(i = 7\) и \(j = 5\), при этом сумма индексов равна \(7 + 5 = 12\), так как \(7\) и \(4\) являются взаимно простыми.
Примеры
| № | Входные данные | Выходные данные |
|
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
|