The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are 
F2 = {1/2} 
F3 = {1/3, 1/2, 2/3} 
F4 = {1/4, 1/3, 1/2, 2/3, 3/4} 
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

You task is to calculate the number of terms in the Farey sequence Fn.

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10 ⁶). There are no blank lines between cases. A line with a single 0 terminates the input.

For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn. 

2

3

4

5

0

1

3

5

9

#include <iostream>

#include <cstring>

using namespace std;

const int MAXN = 1e6+5;

int Phi[MAXN], Prime[MAXN], nPrime;

long long Ans[MAXN];

void Euler()

{

    memset(Phi, 0, sizeof(Phi));

    Phi[1] = 1;

    nPrime = 0;

    for(int i = 2; i < MAXN; i++)

    {

        if(!Phi[i]) //i为素数

        {

            Phi[i] = i - 1;

            Prime[nPrime++] = i;

        }

        for(int j = 0; j < nPrime && (long long)i*Prime[j] < MAXN; j++)

        {

            if(i%Prime[j])

            {

                Phi[ i*Prime[j] ] = Phi[i]*(Prime[j]-1);

            }

            else

            {

                Phi[ i*Prime[j] ] = Phi[i]*Prime[j];

                break;

            }

        }

    }

    return;

}

void solve()

{

    Euler();

    Ans[2] = Phi[2];

    for(int i = 3; i < MAXN; i++)

    {

        Ans[i] = Ans[i-1] + Phi[i];

    }

    return;

}

int main()

{

    int N;

    solve();

    while(cin>>N && N)

    {

        cout << Ans[N] << endl;

    }

    return 0;

}