Wieże

Wieża

Jasiu ma n klocków z napisanymi na nich liczbami naturalnymi. Chce ułożyć z nich jak najwyższą wieżę, kładąc jeden klocek na drugim. Klocki mogą się stykać pod warunkiem, że NWD (Największy Wspólny Dzielnik) liczb na tych klockach jest większy od 1. Pomożesz Jasiowi, jeśli powiesz mu, ile wynosi wysokość najwyższej wieży, jaką może ułożyć z tych klocków.

Zadanie:

Napisz program, który:
• wczyta opis n klocków
• wyznaczy wysokość najwyższej wieży, jaką można zbudować
• wypisze wynik na standardowe wyjście

Wejście:

W pierwszej linii znajduje się jedna liczba całkowita n (1 <= n <= 20). W następnej linii znajduje się n liczb naturalnych mniejszych od 10⁹ - reprezentują one klocki z tymi właśnie liczbami.

Wyjście:

Jedna liczba, określająca wysokość najwyższej wieży, jaką można zbudować.

Przykład:

wejście:
6
7 5 14 10 17 2

wyjście:
5

Wyjaśnienie przykładu:

Jedna z wież o największej wysokości, jaką możnaby zbudować, to na przykład:

5

10

2

14

7