Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из \(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\).
В первом примере подмножество, соответствующее всей последовательности даёт наибольший общий делитель равный \(1\). Все меньшие подмножества дают наибольший общий делитель больший \(1\).
Во втором примере наибольший общий делитель любого подмножества хотя бы \(2\).
3 10 6 15
3
3 2 4 6
-1
7 30 60 21 42 70 15 30
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач