Problem description

Kilka lat temu zaczęła się budowa perły Cesarstwa – niemal doskonałej świątyni z olbrzymią kopułą. Budowa powoli dobiega już końca, jednak do pełnej doskonałości budowli brakuje tylko jednego: mozaiki na posadzce. By mozaika była dobra, musi być zbudowana z kwadratowych kamyczków tego samego rozmiaru, cała musi mieć kształt kwadratu i musi się składać z kamyczków w dokładnie dwóch kolorach.

Twoim zadaniem będzie kupienie na lokalnym targowisku materiałów na tę finalną mozaikę. W sekcji kamieniarskiej targowiska są tylko dwaj kupcy: Kwadratus i Liniusz. Kwadratus sprzedaje tylko białe kamyczki i za K talarów otrzymasz u niego K² kamyczków. Liniusz natomiast sprzedaje droższe, pozłacane kamyczki i za K talarów możesz od niego dostać K kamyczków.

Targowisko jest już bliskie zamknięcia, kupcy chcą już zamykać stanowiska, więc każdemu z dwóch kupców możesz zapłacić tylko jedną monetą. Na ten zakup kwestor przyznał Ci N monet o nominałach A₁, A₂, …, A_N. Nominały w Cesarstwie nie są przypadkowe – dla wygody nominały nie mają dzielników pierwszych większych od 5.

Sytuacja staje się napięta, bo kupcy już zamykają stanowiska, mozaikę trzeba wykonać jak najszybciej, a możliwych zakupów jest dużo. Ale właściwie to jak dużo? Na ile sposobów możesz wręczyć Kwadratusowi i Liniuszowi dwie monety tak, by otrzymane od nich kamyczki mogły wszystkie złożyć się na dobrą mozaikę?

Wejście

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita N, określająca liczbę Twoich monet. W drugim wierszu wejścia znajduje się N liczb całkowitych A₁, A₂, …, A_N pooddzielanych pojedynczymi odstępami i określających nominały kolejnych monet w talarach.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita, określająca liczbę sposobów wręczenia kupcom monet tak, by z uzyskanych w ten sposób kamyczków dało się stworzyć dobrą mozaikę.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ A_i ≤ 10¹⁸, liczby A_i są postaci 2^n_i3^m_i5^k_i dla nieujemnych i całkowitych n_i, m_i, k_i.

Przykład

5
1 1 16 3 5

3

4
2 3 5 5

2

5
3 3 5 3 12

0