FMI NO STRESS 13 | Friendly Numbers

Cerință

Marcel a primit de la bunica sa un sac cu bile care au numere naturale inscripționate pe ele. Bunica sa, Bogdana, i-a spus că unele bile sunt prietenoase, iar unele mai puțin prietenoase, și l-a învățat și cum să își dea seama. Un număr se numește prietenos dacă, în descompunerea sa în factori primi, toți exponenții sunt egali. O bilă se numește prietenoasă dacă are inscripționată pe ea un număr prietenos. De exemplu:

• Bila cu numărul $27000 = 2^3 \cdot 3^3 \cdot 5^3$ este prietenoasă.
• Bila cu numărul $30184 = 2^3 \cdot 3^3 \cdot 11$ nu este prietenoasă.

Marcel se întreabă care este procentul ca extrăgând o singură bilă din sacul primit, aceasta să fie prietenoasă.

Date de intrare

Pe prima linie se găsește un număr natural $N$, care reprezintă numărul de bile din sacul primit, iar pe următoarea linie se găsesc $N$ numere naturale care sunt numerele inscripționate pe bile.

Date de ieșire

Pe prima linie se va găsi un număr natural, care reprezintă procentul ca bila extrasă să fie prietenoasă. Se cere partea întreagă a acestuia. $\lfloor 57.64\% \rfloor = 57\%$

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq x_i \leq 100 \ 000$.

Exemplul 1

stdin

11
1 2 3 4 5 6 7 8 9 10 11

stdout

100

Explicație

Toate numerele sunt prietenoase.

• $2, 3, 5, 7, 11$ sunt numere prime, deci sunt prietenoase.
• $1$ este de asemenea prietenos.
• $4 = 2^2$ are un singur exponent, deci este prietenos.
• $6 = 2^1 \cdot 3^1$ are coeficienții egali cu $1$.
• $9 = 3^2$ are un singur exponent, deci este prietenos.
• $10 = 2^1 \cdot 5^1$ are coeficienții egali cu $1$.

Exemplul 2

stdin

9
12 18 20 24 28 40 44 45 48

stdout

0

Explicație

Niciun număr nu este prietenos.

Exemplul 3

stdin

7
1 12 9 48 7 7 12

stdout

57