#include<cstdio>
#include<bitset>
#include<map>
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Point{
	ull S;
	int x;
	int y;
	Point (const ull &A,const int &X,const int &Y){
		S=A;
		x=X;
		y=Y;
	}
	Point(){
		
	}
};
bool operator < (const Point &a,const Point &b){
	if(a.S!=b.S){
		return a.S<b.S;
	}
	if(a.x!=b.x){
		return a.x<b.x;
	}
	return a.y<b.y;
}
map<Point,vector<int> >ma;
ll ans;
bool vis[100000];
int pri[1000],pr;
void shai(){
	vis[1]=1;
	for(int i=1;i*i<=100000;++i){
		if(!vis[i]){
			pri[pr++]=i;
			for(int j=i*i;j*j<=100000;j+=i){
				vis[j]=1;
			}
		}
	}
}
int n,m,a[1000010];
ll num[100010];
int main(){
//	freopen("e.in","r",stdin);
	shai();
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		++num[a[i]];
	}
	for(int i=1;i<=100000;++i){
		ans+=(num[i]*(num[i]-1ll)*(num[i]-2ll))/6ll;
	}
	sort(a+1,a+n+1);
	int last=1;
	for(int i=1;i<=n;++i){
		if(a[i]!=a[i-1]){
			int x=a[i];
			ull S=0;
			for(int j=0;j<pr-1;++j){
				int cnt=0;
				while(x%pri[j]==0){
					++cnt;
					x/=pri[j];
				}
				if(cnt%2!=0){
					S|=((ull)1<<j);
				}
			}
			int y=0,z;
			while(x%pri[pr-1]==0){
				++y;
				x/=pri[pr-1];
			}
			y%=2;
			z=x;
			vector<int> v=ma[Point(S,y,z)];
			for(int j=0;j<v.size();++j){
				ans+=num[a[i]]*num[v[j]]*num[(int)(sqrt((ll)a[i]*(ll)v[j])+0.5)];
			}
			ma[Point(S,y,z)].push_back(a[i]);
			last=i;
		}
	}
	cout<<ans<<endl;
	return 0;
}