Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из $$$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$$$.
Название |
---|