Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из \(n\) целых чисел \(a_i\).
Разрешается выбрать любое подмножество из них и количество очков равно наибольшему общему делителю выбранных чисел. Игроку нужно выбрать наименьшее количество элементов, получив количество очков, равное \(1\). Теперь Януш интересуется, какое минимальное количество элементов нужно выбрать игроку в таком случае?
Выходные данные
Если нет ни одного подмножества данной последовательности с наибольшим общим делителем равным \(1\), то выведите -1.
Иначе выведите ровно одно целое число — размер минимального множества с наибольшим общим делителем равным \(1\).
Примечание
В первом примере подмножество, соответствующее всей последовательности даёт наибольший общий делитель равный \(1\). Все меньшие подмножества дают наибольший общий делитель больший \(1\).
Во втором примере наибольший общий делитель любого подмножества хотя бы \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 6 15
|
3
|
|
2
|
3
2 4 6
|
-1
|
|
3
|
7
30 60 21 42 70 15 30
|
3
|