Dorel este pasionat de feng shui. Astfel, pentru a-şi crea un cadru adecvat meditaţiei, s-a hotărât să scrie pe pereţii casei numere care au un număr prim de divizori. El a găsit n numere, însă nu ştie să le aleagă pe cele potrivite.

Cerința

Se dau n numere naturale. Aflaţi câte dintre acestea au un număr prim de divizori.

Date de intrare

Fișierul de intrare prim013.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire

Fișierul de ieșire prim013.out va conține pe prima linie numărul de numere care au un număr prim de divizori.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000

Exemplu

prim013.in

5
1 3 6 9 625

prim013.out

3

Explicație

Numerele 3,9,625 au 2,3 respectiv 5 divizori, numărul divizorilor fiind prim. În total sunt 3 numere cu numărul divizorilor prim.

#include <bits/stdc++.h>
using namespace std;
ifstream fin("prim013.in");
ofstream fout("prim013.out");
int prim(int n)
{
    if(n == 0 || n == 1) return 0;
    if(n == 2) return 1;
    if(n % 2 == 0) return 0;
    for(int i = 3 ; i * i <= n ; i += 2) if(n % i == 0) return 0;
    return 1;
}
int nrdiv(int n)
{
    int d = 2 , prod = 1;
    while(n > 1)
    {
        int p = 0;
        while(n % d == 0) {n /= d; p++;}
        if(p) prod = prod * (p+1);
        d++;
        if(d * d > n) d =n;
    }
    return prod;
}
int main()
{
    int n , x , cnt = 0;
    fin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        fin >> x;
        if(x != 1 && prim(nrdiv(x))) cnt++;
    }
    fout << cnt;

    fin.close();
    fout.close();

    return 0;
}