Consider a N*N*N lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0) ? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y. 
 
Input : 
The first line contains the number of test cases T. The next T lines contain an interger N 
 
Output : 
Output T lines, one corresponding to each test case. 
 
Sample Input : 
3 
1 
2 
5 
 
Sample Output : 
7 
19 
175 
 
Constraints : 
T <= 50 
1 <= N <= 1000000

#include<cstdio>#include<iostream>#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endifusing namespace std;typedef long long ll;const int M=1e6+5;int n,m,T;ll sum[M];int tot,prime[M/3],mu[M];bool check[M];void sieve(){    n=1e6;mu[1]=1;    for(int i=2;i<=n;i++){        if(!check[i]) prime[++tot]=i,mu[i]=-1;        for(int j=1;j<=tot&&i*prime[j]<=n;j++){            check[i*prime[j]]=1;            if(!(i%prime[j])){mu[i*prime[j]]=0;break;}            else mu[i*prime[j]]=-mu[i];        }    }    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];}inline ll s2(int x){return 1LL*x*x;}inline ll s3(int x){return 1LL*x*x*x;}inline ll solve(int n){    ll ans=3;    for(int i=1,pos;i<=n;i=pos+1){        pos=n/(n/i);        ans+=s3(n/i)*(sum[pos]-sum[i-1]);        ans+=3*s2(n/i)*(sum[pos]-sum[i-1]);    }    return ans;}int main(){    sieve();    for(scanf("%d",&T);T--;){        scanf("%d",&n);        printf(LL"\n",solve(n));    }    return 0;}