Dzielniki

Limit pamięci: 128 MB

Dany jest zbiór złożony z liczb całkowitych dodatnich. Chcemy znaleźć niepusty podzbiór zbioru zawierający możliwie najmniej elementów, taki że jedynym dodatnim wspólnym dzielnikiem wszystkich liczb ze zbioru jest jedynka.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą rozmiar zbioru . Drugi wiersz zawiera liczb całkowitych dodatnich (), oznaczających poszczególne elementy zbioru .

Wyjście

Jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą: rozmiar szukanego zbioru , lub jedno słowo BRAK, jeśli odpowiedni zbiór nie istnieje.

Przykład

Dla danych wejściowych:

5
6 10 12 15 18

poprawną odpowiedzią jest:

3

natomiast dla danych:

5
2 4 6 8 10

poprawnym wynikiem jest:

BRAK

Autor zadania: Jakub Łącki.