CodeChef submission 136793 (C) plaintext list. Status: TLE, problem SNCK04, contest SNACKDWN. By ContestCrackersTeam (ContestCrackersTeam), 2009-11-21 23:57:54.
#include <stdio.h>
#include <math.h>
 
#define FALSE 0
#define TRUE  (!FALSE)
 
int PrArr[100000];
int NumPr = 0;
 
int IsPrime[1000009];
 
int PrimeFactors[1000];
int NumPrFact;
 
long long int Farey[1000009];
 
void GeneratePrimesUpto( int M )
{
    int i = PrArr[NumPr - 1];
    i += 2;
 
    while ( i <= M )
    {
        int IsPr = TRUE;
        int j = (int)sqrt(i) + 1;
        int k;
 
        for ( k = 0; k < NumPr; k++ )
        {
            int Pr = PrArr[k];
 
            if ( Pr > j )
            {
                break;
            }
 
            if ( ( i % Pr ) == 0 )
            {
                IsPr = FALSE;
                break;
            }
        }
 
        if ( IsPr )
        {
            PrArr[NumPr++] = i;
            IsPrime[i] = TRUE;
        }
 
        i += 2;
    }
}
 
/*
void PrimeFactorise( int m )
{
    int Limit = (int)sqrt( m ) + 1;
    int i;
 
    NumPrFact = 0;
 
    for ( i = 0; i < NumPr; i++ )
    {
        int Pr = PrArr[i];
        if ( Pr > Limit )
        {
            break;
        }
        if ( ( m % Pr ) == 0 )
        {
            PrimeFactors[NumPrFact++] = Pr;
            while ( ( m % Pr ) == 0 )
            {
                m /= Pr;
            }
 
            if ( m == 1 )
            {
                break;
            }
        }
    }
    if ( m != 1 )
    {
        PrimeFactors[NumPrFact++] = m;
    }
}
*/
 
void PrimeFactorise( int m )
{
    int i;
 
    NumPrFact = 0;
 
    if ( m == 1 )
    {
        return;
    }
 
    for ( i = 0; i < NumPr; i++ )
    {
        if ( IsPrime[m] )
        {
            PrimeFactors[NumPrFact++] = m;
            break;
        }
        else
        {
            int Limit = (int)sqrt( m ) + 1;
            int Pr = PrArr[i];
 
            if ( Pr > Limit )
            {
                break;
            }
 
            if ( ( m % Pr ) == 0 )
            {
                PrimeFactors[NumPrFact++] = Pr;
                while ( ( m % Pr ) == 0 )
                {
                    m /= Pr;
                }
 
                if ( m == 1 )
                {
                    break;
                }
            }
        }
    }
}
 
int Euler( int n )
{
    int Totient;
    int i;
 
    PrimeFactorise( n );
 
    Totient = n;
 
    for ( i = 0; i < NumPrFact; i++ )
    {
        Totient /= PrimeFactors[i];
        Totient *= PrimeFactors[i] - 1;
    }
 
    return Totient;
}
 
int main( void )
{
    int i, T;
    int n;
 
    PrArr[0] = 2;
    IsPrime[2] = TRUE;
    PrArr[1] = 3;
    IsPrime[3] = TRUE;
    NumPr = 2;
 
    GeneratePrimesUpto( 1000000 );
 
    Farey[1] = 2;
 
    for ( i = 2; i <= 1000000; i++ )
    {
        Farey[i] = Farey[i - 1] + Euler( i );
    }
 
    /* printf( "NumPr: %d\n", NumPr ); */
 
    scanf( "%d", &T );
 
    while ( T > 0 )
    {
        scanf( "%d", &n );
        printf( "%lld\n", Farey[n] - 2 );
        T--;
    }
 
    return 0;
}