import std.stdio, std.string, std.conv;
import std.algorithm, std.array, std.range;
import std.bigint, std.math;
 
auto solve(string s_)
{
    immutable N = s_.to!int();
    auto AS = new long[N];
    foreach(ref v;AS) v=readln.chomp().to!long();
    immutable M=AS.reduce!max();
    immutable M2=sqrt(M.to!real()).to!long()+1;
    immutable M3=cbrt(M.to!real()).to!long()+1;
    auto pbs = new bool[M2]; pbs[]=true;
    long[] ps;
    size_t q=M2;
    foreach(i;2..M2) if(pbs[i])
    {
        if(q==M2 && i>=M3) q=ps.length;
        ps~=i;
        for(auto j=i*2; j<M2; j+=i) pbs[j]=false;
    }
    if(q==M2) q=ps.length;
    auto RS = new long[N];
    int[long] b; b[1]=0;
    foreach(k;0..N)
    {
        BigInt r=1;
        auto a=1,v=AS[k];
        foreach(p;ps[0..q])
        {
            int c=0;
            while(v%p==0) v/=p, ++c;
            c%=3;
            if(c!=0)
            {
                foreach(_;0..c) a*=p;
                foreach(_;0..3-c) r*=p;
            }
        }
        if(v>1)
        {
            a*=v;
            long lo=0, hi=ps.length-1;
            void rev()
            {
                while(lo<=hi)
                {
                    auto m=(lo+hi)/2;
                    immutable p=ps[m], pp=p*p;
                    if(pp==v){ r*=p; return; }
                    if(pp<v) lo=m+1;
                    else     hi=m-1;
                }
                r*=v*v;
            }
            rev();
        }
        AS[k]=a;
        auto t=r>M? -1: r.toLong();
        RS[k]=t;
        if(a !in b) b[a]=1;
        else ++b[a];
        if(t !in b) b[t]=0;
    }
    b[1]=min(1,b[1]);
    bool[long] u;
    int m=0;
    foreach(k;0..N)
    {
        immutable a=AS[k];
        if(a in u) continue;
        immutable r=RS[k];
        if(r in u) m-=b[r];
        m+=max(b[a],b[r]);
        u[a]=true,u[r]=true;
    }
    return m;
}
void main(){ for(string s; (s=readln.chomp()).length;) writeln(solve(s)); }