1 #include <cstdio>
 2 typedef long long ll;
 3 const ll N=1000001;
 4 ll n,phi[N],pri[N],bo[N];
 5 void makepri(){
 6     for (ll i=2;i<=N;i++){
 7         if (!bo[i]){
 8             pri[++pri[0]]=i;
 9             phi[i]=i-1;
10         }
11         for (ll j=1;j<=pri[0] && i*pri[j]<=N;j++){
12             bo[i*pri[j]]=1;
13             if (i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
14             else{
15                 phi[i*pri[j]]=phi[i]*pri[j];
16                 break;
17             }
18         }
19     }
20 }
21 int main(){
22     makepri();
23     for (ll i=1;i<=N;i++) phi[i]+=phi[i-1];
24     while (scanf("%I64d",&n),n) printf("%I64d
",phi[n]);
25 }