/*

题意： 给出n个数（n<100000）, 每个数都不大于100000，数字不会有重复。现在随意抽出3个，问三个彼此互质 或者 三个彼此不互质的数目有多少。

思路： 这道题反着想，就是三个数中只有一对互质 或者只有两对互质的个数。

研究后发现 对于每个数字求出与其不互质的个数k   那么  sum ( k*(n-1-k) )/2 就是相反的数目， 所以最终的答案就是 C(n,3) -  sum ( k*(n-1-k) )/2.

*/

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef __int64 LL;

const int maxn=;

int prime[maxn],flag[maxn],num;

int numc[maxn*+],f[maxn*+];

int factor[],fac;

LL sum;

void getprimes()

{

    memset(flag,,sizeof(flag));

    int i,j;num=;

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

    {

        if(flag[i]) prime[num++]=i;

        for(j=;j<num && prime[j]*i<maxn;j++)

        {

            flag[prime[j]*i]=;

            if(i%prime[j]==) break;

        }

    }

}

void dfs1(int now,int s)//找出它所有的因子

{

    if(now==fac)

    {

        numc[s]++;

        return ;

    }

    dfs1(now+,s);

    dfs1(now+,s*factor[now]);

}

void dfs2(int id,int all,int now,int s )

{

    if(now==all)

    {

        sum+=numc[s];

        return ;

    }

    if(id<fac)

    {

        dfs2(id+,all,now+,s*factor[id]);

        dfs2(id+,all,now,s);

    }

}

void getfactors(int n)//分解质因子

{

    int i;fac=;

    for(i=;i<num && prime[i]<=n;i++)

    {

        if(n%prime[i]==)

        {

            factor[fac++]=prime[i];

            while(n%prime[i]==) n/=prime[i];

        }

    }

    if(n>) factor[fac++]=n;

}

int main()

{

    getprimes();

    int t,n,i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        memset(numc,,sizeof(numc));

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

        {

            scanf("%d",f+i);

            getfactors(f[i]);

            dfs1(,);

        }

        LL ans=;

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

        {

            getfactors(f[i]);

            LL ret=,temp=;

            for(j=;j<=fac;j++)//容斥原理找出与它不互质的个数

            {

                sum=;

                dfs2(,j,,);

                temp+=ret*sum;

                ret=-ret;

            }

            if(temp==) continue;//当f[i]==1时，所有数都与它不互质的是0个

            ans+=(temp-)*(n-temp);

        }

        printf("%I64d\n",(LL)n*(n-)*(n-)/-ans/);

    }

    return ;

}