/***

 大意：计算gcd（x，y，z） =1     0<= x, y , z <= n 问有多少个这样的对

 莫比乌斯反演：（反演： 用结果推原因）

 函数m(m)的定义如下：

 莫比乌斯反演：

     * f(x) = sigma{g(d)}其中x % d == 0，则g(x) = sigma{miu(d) * f(x/d)}

     * f(x) = sigma{g(d)}其中d % x == 0，则g(x) = sigma{miu(d/x) * f(d)}

 莫比乌斯反演中miu(x) = 

     * 1   {x中含有偶数个不同的质因子}

     * -1  {x中含有奇数个不同的质因子}

     * 0   {其他情况}

 本题： 设f(x) = 约数为x 的所有数集合   g(x) = 最大公约数gcd 为x的集合

 那么g(x) = siga(mu(d)*f(x/d)) x%d==0

 或者 g(x) =  siga(mu(d/x) *f（d）) d%x==0

 在本题中只包含了x,y,z>1  情况 ，，还应加上退化到3个平面上的情况。。

 1、 f(x) = n/x*n/x*n/x；----〉 g（x） = mu[i] *（n/x*n/x*n/x）

 2、 加上退化到三个平面   ----〉 g（x） = mu[i]*（n/x+1）*（n/x+1）*（n/x+1）

 或者分开求：

 1、 三个坐标轴。。3

 2、 空间中 n/x* n/x*n/x;

 3、 三个坐标平面: n/x*n/x +n/x*n/x +n/x*n/x

 **/

 1、 第一种方法



 #include <iostream>

 #include <cstring>

 using namespace std;

 const int  maxn = ;

 int pri[maxn];

 int prime[maxn];

 int mu[maxn];

 void pri_mu(){

     memset(prime,,sizeof(prime));

     int cnt =;

     mu[] =;

     for(int i=;i<maxn;i++){

         if(!prime[i]){

             mu[i] =-;

             pri[cnt++] = i;

         }

         for(int j=;j<cnt;j++){

             if(i*pri[j]>maxn)

                 break;

             prime[i*pri[j]] = ;

             if(i%pri[j]==){

                 mu[i*pri[j]] =;

                 break;

             }else

                 mu[i*pri[j]] = -mu[i];

         }

     }

 }

 int main()

 {

     pri_mu();

     int t;

     cin>>t;

     long long  n;

     while(t--){

         cin>>n;

         long long ans =;

         for(int i=;i<=n;i++)

             ans += (long long )mu[i]*((n/i+)*(n/i+)*(n/i+)-);

         cout<<ans<<endl;

     }

     return ;

 }

 ----------------------------------------------------------------------------------------------------------
2、 第二种方法

 #include <iostream>

 #include <cstring>

 using namespace std;

 const int  maxn = ;

 int pri[maxn];

 int prime[maxn];

 int mu[maxn];

 void pri_mu(){

     memset(prime,,sizeof(prime));

     int cnt =;

     mu[] =;

     for(int i=;i<maxn;i++){

         if(!prime[i]){

             mu[i] =-;

             pri[cnt++] = i;

         }

         for(int j=;j<cnt;j++){

             if(i*pri[j]>maxn)

                 break;

             prime[i*pri[j]] = ;

             if(i%pri[j]==){

                 mu[i*pri[j]] =;

                 break;

             }else

                 mu[i*pri[j]] = -mu[i];

         }

     }

 }

 int main()

 {

     pri_mu();

     int t;

     cin>>t;

     long long  n;

     while(t--){

         cin>>n;

         long long ans =;

         for(int i=;i<=n;i++)

             ans += (long long )mu[i]*((n/i)*(n/i)*(n/i+));

         cout<<ans<<endl;

     }

     return ;

 }