D. Взаимно простые
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив из $$$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$$$).

Входные данные

Входные данные состоят из нескольких наборов. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10$$$) — количество наборов. Далее следует их описание.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — количество элементов в массиве.

Следующая строка содержит $$$n$$$ разделенных пробелами положительных чисел $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора выведите одно целое число  — максимальное значение $$$i + j$$$, такое, что $$$i$$$ и $$$j$$$ удовлетворяют условию, что $$$a_i$$$ и $$$a_j$$$ взаимно просты, или выведите $$$-1$$$, если не существует таких $$$i$$$ и $$$j$$$.

Пример
Входные данные
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
Примечание

Для первого примера можно выбрать $$$i = j = 3$$$, при этом сумма индексов равна $$$6$$$, так как $$$1$$$ и $$$1$$$ - взаимно простые.

Для второго примера можно выбрать $$$i = 7$$$ и $$$j = 5$$$, при этом сумма индексов равна $$$7 + 5 = 12$$$, так как $$$7$$$ и $$$4$$$ являются взаимно простыми.