Untitled

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define ll long long

#define file \
  freopen("matrix.in", "r", stdin);
//  freopen("output.txt", "w", stdout)

#define OJudge(in,out) \
      freopen(in, "r", stdin);\
      freopen(out, "w", stdout)


#define FIn   \
  cin.tie(0); \
  cout.tie(0); \
  ios_base::sync_with_stdio(false)

#define endl '\n'

#define all(x) x.begin(), x.end()

const string IN = "input.txt";
const string OUT = "output.txt";

typedef long double T;
typedef complex<T> pt;
//#define x real()
//#define y imag()
//const ll p = 998244353;
int tc;
//const T pi = 3.1415926535897;
string alpha = "abcdefghijklmnopqrstuvwxyz";
typedef pair<int,int> pii;


struct cmp {
    bool operator()(const pair<pii, int> &p1, const pair<pii,int> &p2) const {
        return p1.first < p2.first;
    }
};

int n, f, m, P;
int z, y;
const int N = 1e6 + 5;


void pre();
void solve(int tc) {
    int x, ans = 0;
    cin >> n;
    map<ll, ll> freq;
    for (int i = 0; i < n; i++) {
        cin >> x;
        map<ll, ll> have;
        for (int p = 2; p * p <= x && p <= 1000; p++) {
            if (x % p)
                continue;
            int cnt = 0;
            while(x % p == 0) {
                cnt++, x/=p;
            }
            if (cnt % 3) {
                have[p] = cnt % 3;
            }
        }
        if (x > 1)
            ++have[x];
        ll need = 1;
        for (auto it : have) {
            need *= it.first;
            if (it.second == 2) {
                need *= it.first;
            }
        }
        ans += freq[need]++;
    }
    cout << ans << '\n';
}

signed main() {
    FIn;

#ifndef ONLINE_JUDGE
    OJudge(IN.c_str(),OUT.c_str());
#endif

//    file;
    pre();
    tc = 1;
    cin >> tc;
    for(int i = 1; i <= tc; i++) {
//        cout << "Case #" << i <<": ";
        solve(i);
    }
}

void pre() {

}