/*题意： 给出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=1000;int prime[maxn],flag[maxn],num;int numc[maxn*100+5],f[maxn*100+5];int factor[20],fac;LL sum;void getprimes(){    memset(flag,1,sizeof(flag));    int i,j;num=0;    for(i=2;i<maxn;i++)    {        if(flag[i]) prime[num++]=i;        for(j=0;j<num && prime[j]*i<maxn;j++)        {            flag[prime[j]*i]=0;            if(i%prime[j]==0) break;        }    }}void dfs1(int now,int s)//找出它所有的因子{    if(now==fac)    {        numc[s]++;        return ;    }    dfs1(now+1,s);    dfs1(now+1,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+1,all,now+1,s*factor[id]);        dfs2(id+1,all,now,s);    }}void getfactors(int n)//分解质因子{    int i;fac=0;    for(i=0;i<num && prime[i]<=n;i++)    {        if(n%prime[i]==0)        {            factor[fac++]=prime[i];            while(n%prime[i]==0) n/=prime[i];        }    }    if(n>1) factor[fac++]=n;}int main(){    getprimes();    int t,n,i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        memset(numc,0,sizeof(numc));        for(i=1;i<=n;i++)        {            scanf("%d",f+i);            getfactors(f[i]);            dfs1(0,1);        }        LL ans=0;        for(i=1;i<=n;i++)        {            getfactors(f[i]);            LL ret=1,temp=0;            for(j=1;j<=fac;j++)//容斥原理找出与它不互质的个数            {                sum=0;                dfs2(0,j,0,1);                temp+=ret*sum;                ret=-ret;            }            if(temp==0) continue;//当f[i]==1时，所有数都与它不互质的是0个            ans+=(temp-1)*(n-temp);        }        printf("%I64d\n",(LL)n*(n-1)*(n-2)/6-ans/2);    }    return 0;}