#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long LL;

const int N=1e6+;

const int INF=0x3f3f3f3f;

int vis[N],prime[],cnt;

void getprime(){

  bool v[];

  memset(v,,sizeof(v));

  for(int i=;i*i<=;++i){

    if(v[i])continue;

    for(int j=i*i;j<=;j+=i)

      v[j]=;

  }

  for(int i=;i<=;++i)

    if(!v[i])prime[++cnt]=i;

}

int main(){

    int T,n;

    getprime();

    // printf("%d\n",cnt);

    scanf("%d",&T);

    while(T--){

      memset(vis,,sizeof(vis));

      scanf("%d",&n);

      LL ans=;

      for(int i=;i<=n;++i){

        LL t,t1;scanf("%lld",&t),t1=t,t=;

        LL aim=;bool flag=;

        for(int j=;j<=cnt&&prime[j]<=t1/prime[j];++j){

            int tmp=;

            while(t1%prime[j]==)t1/=prime[j],++tmp;

            if(tmp%==){

              t*=prime[j];

              aim*=prime[j];

              if(aim>N-)flag=;

              aim*=prime[j];

              if(aim>N-)flag=;

            }

            else if(tmp%==){

              t*=prime[j]*prime[j];

              aim*=prime[j];

              if(aim>N-)flag=;

            }

        }

        if(!flag){

          if(t1>){

            t*=t1;

            aim*=t1;

            if(aim>N-)flag=;

            aim*=t1;

            if(aim>N-)flag=;

          }

          if(!flag)ans+=vis[aim];

        }

        ++vis[t];

      }

      printf("%lld\n",ans);

    }

    return ;

}