#include <iostream>
#include <fstream>
#include <string>


using namespace std;

string x;

unsigned long long p[10][65];

int main()
{
    int q,rez=0;
    ifstream f("dtcsu.in");
    ofstream g("dtcsu.out");
    for(int i=1;i<=276997;++i)
        getline(f,x);
    f>>q;
    p[1][1]=2;
    for(int i=2;i<=59;++i)
        p[1][i]=p[1][i-1]*p[1][i-1];
    p[2][1]=3;
    for(int i=2;i<=37;++i)
        p[2][i]=p[2][i-1]*p[2][i-1];
    p[3][1]=5;
    for(int i=2;i<=25;++i)
        p[3][i]=p[3][i-1]*p[3][i-1];
    p[4][1]=7;
    for(int i=2;i<=21;++i)
        p[4][i]=p[4][i-1]*p[4][i-1];
    p[5][1]=11;
    for(int i=2;i<=17;++i)
        p[5][i]=p[5][i-1]*p[5][i-1];
    for(;q;--q)
    {
        long long x;

        f>>x;
        for(int i=59;i>=1;--i)
        {
            for(int j=1;j<=5;++j)
                if(p[j][i] && x%p[j][i]==0)
                    {

                        x/=p[j][i];
                    }
        }

        if(x==1)
            ++rez;
    }
    g<<rez;
    return 0;
}