【题目描述】：
    在XYZ的dzy loves math6问世后，dzy一直觉得这道题答案太大，一点都不优美，于是他随手在外面套上一个μ。同时，他又觉得输入两个数实在太麻烦，于是题目变成了：

    你能解决这个问题吗？
【题目解法】：
    首先我们知道只有不含有平方因子的数mu才不为0
    因此gcd(i,j)=1（不会html别打我TAT...）
    所有ans=sigma(mu(ij)*sigma(mu[d]){d|i d|j})=sigma(mu(i)*sigma(mu(d)*g(i,d){d|i}))
    其中g(i,d)=sigma(mu(d)+mu(2d)+...+mu(n))
    因此我们可以枚举i，然后计算此时的答案与ans[i-1]累加即为ans[i]
    首先我们知道mu(i)!=0，因此i不含有平方因子，然后把i分解质因数最多只有log级别个大概是20+
    因此我们可以暴力枚举i的因子，然后计算g
    我们知道g(i-d,d)的答案已经知道，g(i,d)=g(i-d,d)+mu(i)
    因此每次更新g即可，然后根据上面的式子计算即可
    然而我发现分解质因数的方法太慢了！！！
    然后去%claris的程序，发现我们可以预处理出minnum[i]表示i的最小质因子
    然后就可以在log的时间下求出所有的质因子，而且速度很快！%%%claris

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=10000005;
int n,m,prime[N],mobius[N],tot,ans[N],minnum[N];
bool v[N]; int g[N],delta,cnt,p[N],nowans,a[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    m=getint();
    for (int i=1; i<=m; i++) a[i]=getint(),n=max(n,a[i]);
    memset(v,true,sizeof(v)); mobius[1]=1;
    for (int i=2; i<=n; i++)
    {
        if (v[i]) prime[++tot]=i,mobius[i]=-1,minnum[i]=i;
        for (int j=1; j<=tot; j++)
        {
            if ((long long)i*prime[j]>n) break;
            v[i*prime[j]]=false; minnum[i*prime[j]]=prime[j];
            mobius[i*prime[j]]=-mobius[i];
            if (i%prime[j]==0) {mobius[i*prime[j]]=0; break;}
        }
    }
}
void dfs(int x,int val)
{
    if (x>cnt)
    {
        g[val]+=delta;
        nowans+=mobius[val]*g[val];
        return;
    }
    dfs(x+1,val); dfs(x+1,val*p[x]);
}
void build()
{
    for (int i=1; i<=n; i++)
    {
        ans[i]=ans[i-1]; if (mobius[i]==0) continue; cnt=0;
        for (int x=i;x>1;x/=minnum[x]) p[++cnt]=minnum[x];
        delta=mobius[i]; nowans=0; dfs(1,1);
        ans[i]+=delta*nowans;
    }
}
void solve()
{
    for (int i=1; i<=m; i++) printf("%d\n",ans[a[i]]);
}
int main()
{
    init();
    build();
    solve();
    return 0;
}