dk

Dk

== include(page="template/taskheader" task_id="dk") ==

Taranului Victor ii e foame. Din pacate a cam ramas fara bani si nu are cu ce sa-si plateasca shaorma. Cei de la Dristor Kebab i-au propus un targ greu de refuzat: vanzatorul ii da Taranului o foaie cu $N$ numere, iar flamandul Taran primeste o shaorma gratis daca raspunde repede cate din cele $N$ numere de pe foaie sunt prime.

Taranului Victor ii e foame. Din pacate a cam ramas fara bani si nu are cu ce sa-si plateasca shaorma. Cei de la Dristor Kebab i-au propus un targ greu de refuzat: vanzatorul ii da Taranului o foaie cu $N$ numere, iar flamandul Taran primeste o shaorma gratis daca raspunde repede cate din cele $N$ numere de pe foaie sunt prime. Fiind foarte infometat Victor va cere ajutorul.

h2. Cerinta

h2. Date de intrare

Pe prima linie a fisierului de intrare $dk.in$ se gaseste numarul natural $N$ (numarul de numere de pe foaie)
 
Pe urmatoarele $N$ linii se dau cele $N$ numere, cate unul pe linie
 
x ~1~
x ~2~
...
x ~n~

Pe prima linie a fisierului de intrare $dk.in$ se gaseste numarul natural $N$ (numarul de numere de pe foaie). Pe urmatoarele $N$ linii se dau cele $N$ numere $X{~1~}, X{~2~}, ..., X{~n~}$ cate unul pe linie.

h2. Date de iesire

In fisierul de iesire $dk.out$ se va afisa numarul cerut.

In fisierul de iesire $dk.out$ se va afisa valoarea ceruta.

h2. Restrictii

* $1 ≤ N ≤ 100000$
* $1 ≤ x ~i~ ≤ 10 ^16^$
 

* $1 ≤ N ≤ 400 000$
* $1 ≤ X{~i~} ≤ 10^9^$
* Pentru $20%$ din teste $1 ≤ N ≤ 1 000$
* Pentru alte $20%$ din teste $1 ≤ N ≤ 100 000$

h2. Exemplu

  2
  11
  9

| 3

| 3 |

h3. Explicatie

...

Numerele prime sunt $3$, $2$ si $11$.

== include(page="template/taskfooter" task_id="dk") ==

2159