E. НАСТОЯЩАЯ Теория чисел от Ехаба
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$, который имеет специальное условие: каждый элемент в этом массиве имеет не более 7 делителей. Найдите длину кратчайшей непустой подпоследовательности этого массива, произведение элементов которой является полным квадратом.

Последовательность $$$a$$$ является подпоследовательностью массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$, удалив несколько (возможно, ноль или все) элементов.

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

Первая строка содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.

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

Выведите длину кратчайшей непустой подпоследовательности $$$a$$$, произведение элементов которой является полным квадратом. Если существует несколько таких кратчайших подпоследовательностей, вы можете найти любую из них. Если такой подпоследовательности нет, выведите «-1».

Примеры
Входные данные
3
1 4 6
Выходные данные
1
Входные данные
4
2 3 6 6
Выходные данные
2
Входные данные
3
6 15 10
Выходные данные
3
Входные данные
4
2 3 5 7
Выходные данные
-1
Примечание

В первом примере, вы можете выбрать подпоследовательность $$$[1]$$$.

Во втором примере, вы можете выбрать подпоследовательность $$$[6, 6]$$$.

В третьем примере, вы можете выбрать подпоследовательность $$$[6, 15, 10]$$$.

В четвертом примере, такой подпоследовательности не существует.