#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a,b,e;
int f[N];//存的数
int ans;

struct node{
  int yz[N][2];
  int num;
  int no;
}dx[N];

void divide(int x)//i  底数  s   指数
{
    e=1;
    for(int i=2;i<=x/i;i++) 
    {                         
        if(x%i==0)   
        {
            int s=0;   
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            
            dx[b].yz[e][0]=i;
            if(s/2==0) dx[b].yz[e][1]=s;
            e++;
        }
    }
    if(x>1) 
    {
        //x    1 最后一个 质因数   次数为一
        dx[b].yz[e][0]=x;
        dx[b].yz[e][1]=1;
    }
    e++;
    for(int j=1;j<e;j++)
    {
        dx[b].yz[e][2]+=dx[b].yz[j][0]^(dx[b].yz[j][1])%2;
    }
    f[dx[b].yz[e][2]]++;
}


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
      cin>>dx[i].num;
      a=dx[i].num;
      b=i;
      dx[i].no=i;
      divide(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]!=0)
            ans++;
    }
    cout<<ans;
    return 0;
}