显然当且仅当$\gcd(i,j)=1$时才对答案有贡献，化简得
\[\begin{eqnarray*}
ans&=&\sum_{i=1}^n\sum_{j=1}^i\mu(ij)[\gcd(i,j)=1]\\
&=&\sum_{i=1}^n\sum_{j=1}^i\mu(ij)\sum_{d|i,d|j}\mu(d)\\
&=&\sum_{i=1}^n\mu(i)\sum_{d|i}\mu(d)\sum_{j=1}^{\frac{i}{d}}\mu(dj)
\end{eqnarray*}\]
设
\[S(i,d)=\sum_{j=1}^{\frac{i}{d}}\mu(dj)\]
则
\[ans=\sum_{i=1}^n\mu(i)\sum_{d|i}\mu(d)S(i,d)\]
当且仅当$i$是square-free的时候，才对答案有贡献。此时将$i$分解质因数，然后暴力搜索所有约数，一边搜索一边更新$S(i,d)$以及$ans$即可。
#include<cstdio>
#define N 10000010
int T,n,i,j,A,B,q[1010],tot,p[700000],v[N],s[N];char mu[N];short f[N];
void dfs(int x,int y){
if(x==tot){
f[y]+=A;
if(mu[y]>0)B+=f[y];else B-=f[y];
return;
}
dfs(x+1,y*p[x]),dfs(x+1,y);
}
int main(){
scanf("%d",&T);
for(i=1;i<=T;i++){
scanf("%d",&q[i]);
if(q[i]>n)n=q[i];
}
for(mu[1]=v[1]=1,i=2;i<=n;i++){
if(!v[i])p[tot++]=v[i]=i,mu[i]=-1;
for(j=0;j<tot;j++){
if(i*p[j]>n)break;
v[i*p[j]]=p[j];
if(i%p[j])mu[i*p[j]]=-mu[i];else break;
}
}
for(i=1;i<=n;i++){
s[i]=s[i-1];
if(mu[i]){
for(tot=0,j=i;j>1;j/=v[j])p[tot++]=v[j];
A=mu[i],B=0,dfs(0,1);
if(mu[i]>0)s[i]+=B;
if(mu[i]<0)s[i]-=B;
}
}
for(i=1;i<=T;i++)printf("%d\n",s[q[i]]);
return 0;
}