Code:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 1000006
#define M 1000004
#define ll long long
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}
char pbuf[100000],*pp=pbuf;
int cnt,edges;
bool vis[maxn];
int mu[maxn],prime[maxn],hd[maxn],to[maxn*15],nex[maxn*15];
ll sumv[maxn];
int main()
{
// setIO("input");
int i,j;
mu[1]=1;
for(i=1;i<=M;++i)
for(j=i;j<=M;j+=i)
{
nex[++edges]=hd[j], hd[j]=edges,to[edges]=i;
}
sumv[1] = 1;
for(i=2;i<=M;i++)
{
if(!vis[i]) prime[++cnt]=i,sumv[i] = 1-i;
for(j=1;j<=cnt && i*prime[j] <= M;j ++ )
{
vis[i*prime[j]]=true;
if(i%prime[j]==0) {sumv[i*prime[j]]=sumv[i]; break;}
else sumv[i*prime[j]] = sumv[i] * sumv[prime[j]];
}
}
int T=rd(),n;
ll re=0;
while(T--)
{
n=rd();
re=0;
for(i=hd[n];i;i=nex[i]) re+=sumv[to[i]]*(n/to[i])*(n/to[i]+1)/2;
re*=n;
printf("%lld\n",re);
}
return 0;
}