//互质与欧拉函数

/*

求欧拉函数

按欧拉函数计算公式，只要分解质因数即可

*/

int phi(int n){

    int ans=n;

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

        if(n%i==){

            ans=ans/i*(i-);

            while(n%i==) n/=i;

        }

    }

    if(n>) ans=ans/n*(n-);

    return ans;

} 

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int phi[];

void euler(int n){//用era筛的思路O(nlogn)复杂度

    for(int i=;i<=n;i++)phi[i]=i;

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

        if(phi[i]==i)//i是质数

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

                phi[i*j]=phi[i*j]/i*(i-);

}

int main(){

    int t,n;

    euler();

    scanf("%d",&t);

    for(int tt=;tt<=t;tt++){

        scanf("%d",&n);

        int ans=;

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

            ans+=*phi[i];

        printf("%d %d %d\n",tt,n,ans+);

    }

} 

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int phi[];

int m,v[],prime[];

void euler(int n){//用era筛的思路O(nlogn)复杂度

    memset(v,,sizeof v);

    m=;

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

        if(v[i]==){//i是质数

            v[i]=i,prime[++m]=i;

            phi[i]=i-;

        }

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

            if(prime[j]>v[i] || prime[j]*i>n) break;

            v[i*prime[j]]=prime[j];

            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-://φ(n)=φ(n/p)*(p-1) 性质4

                                                prime[j]);//φ(n)=φ(n/p)*p 性质3

        }

    }

}

int main(){

    int t,n;

    euler();

    scanf("%d",&t);

    for(int tt=;tt<=t;tt++){

        scanf("%d",&n);

        int ans=;

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

            ans+=*phi[i];

        printf("%d %d %d\n",tt,n,ans+);

    }

}