1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 const int N=1e6+10;
5 const int INF=0x3f3f3f3f;
6 int cas=1,T;
7 int c[N];
8 void init()
9 {
10 memset(c,0,sizeof(c));
11 c[1]=1;
12 for(int i=1;i<N;i++)
13 {
14 if(c[i]) for(int j=i<<1;j<N;j+=i) c[j]-=c[i];
15 c[i]+=c[i-1];
16 }
17 }
18 int p[N],vis[N],pn;
19 void getMu(int *mu) //O(n)
20 {
21 memset(vis,0,sizeof(vis));
22 mu[1]=1;
23 pn=0;
24 for(int i=2; i<N; i++)
25 {
26 if(!vis[i]) { p[pn++]=i;mu[i]=-1; }
27 for(int j=0; j<pn&&i*p[j]<N; j++)
28 {
29 vis[i*p[j]]=1;
30 if(i%p[j]) mu[i*p[j]]=-mu[i];
31 else { mu[i*p[j]]=0;break;}
32 }
33 mu[i]+=mu[i-1];
34 }
35 }
36 int main()
37 {
38 //freopen("1.in","w",stdout);
39 //freopen("1.in","r",stdin);
40 //freopen("1.out","w",stdout);
41 //init();
42 getMu(c);
43 scanf("%d",&T);
44 while(T--)
45 {
46 int n;
47 scanf("%d",&n);
48 LL ans=0;
49 //for(int i=1;i<=n;i++) if(c[i]) ans+=c[i] * ((LL) (n/i+1)*(n/i+1)*(n/i+1)-1);
50 for(int i=1;i<=n;)
51 {
52 int x=n/i;
53 int y=n/x;
54 ans+=(c[y]-c[i-1]) * ((LL) (n/i+1)*(n/i+1)*(n/i+1)-1);
55 i=y+1;
56 }
57 printf("%lld
",ans);
58 }
59 //printf("time=%.3lf
",(double)clock()/CLOCKS_PER_SEC);
60 return 0;
61 }