Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Сделай единицу
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из $$$n$$$ целых чисел $$$a_i$$$.

Разрешается выбрать любое подмножество из них и количество очков равно наибольшему общему делителю выбранных чисел. Игроку нужно выбрать наименьшее количество элементов, получив количество очков, равное $$$1$$$. Теперь Януш интересуется, какое минимальное количество элементов нужно выбрать игроку в таком случае?

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

Первая строка содержит единственное целое число $$$n$$$ ($$$1 \le n \le 300\,000$$$) — количество чисел в последовательности.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300\,000$$$).

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

Если нет ни одного подмножества данной последовательности с наибольшим общим делителем равным $$$1$$$, то выведите -1.

Иначе выведите ровно одно целое число — размер минимального множества с наибольшим общим делителем равным $$$1$$$.

Примеры
Входные данные
3
10 6 15
Выходные данные
3
Входные данные
3
2 4 6
Выходные данные
-1
Входные данные
7
30 60 21 42 70 15 30
Выходные данные
3
Примечание

В первом примере подмножество, соответствующее всей последовательности даёт наибольший общий делитель равный $$$1$$$. Все меньшие подмножества дают наибольший общий делитель больший $$$1$$$.

Во втором примере наибольший общий делитель любого подмножества хотя бы $$$2$$$.