#include <stdio.h>

//Count the fractions P/Q, where 1 <= P, Q <= N, where N is a strict positive integer less or equal to 1000000

//KEYPOINT: Euler's totient function

#define INPUT "Fractii.in"
#define OUTPUT "Fractii.out"

#define MAX_N 1000000

#define SPLIT 1000000000

//define the number of prime numbers less or equal to sqrt(MAX_N)
#define PRECOMPUTED_PRIMES_COUNT 169

unsigned short PrecomputedPrimes[PRECOMPUTED_PRIMES_COUNT] = 
				{	
					2,		3,		5,		7,		11,		 13,	17,		19,		23,		29,		31, 
				   37, 	   41,     43,     47,		53, 	 59,	61,		67,		71,		73,		79,
				   83,	   89,	   97,	  101,	   103,		107,   109,	   113,    127,    131,	   137,
				  139,    149,    151,    157,     163,     167,   173,    179,    181,    191,    193,
				  197,    199,    211,    223,     227,     229,   233,    239,    241,    251,    257,
				  263,    269,    271,    277,     281,     283,   293,    307,    311,    313,    317,
				  331,    337,    347,    349,     353,     359,   367,    373,    379,    383,    389,
				  397,    401,    409,    419,     421,     431,   433,    439,    443,    449,    457,
				  461,    463,    467,    479,     487,     491,   499,    503,    509,    521,    523,
				  541,    547,    557,    563,     569,     571,   577,    587,    593,    599,    601,
				  607,    613,    617,    619,     631,     641,   643,    647,    653,    659,    661,
				  673,    677,    683,    691,     701,     709,   719,    727,    733,    739,    743,
				  751,    757,    761,    769,     773,     787,   797,    809,    811,    821,    823,
				  827,    829,    839,    853,     857,     859,   863,    877,    881,    883,    887,
				  907,    911,    919,    929,     937,     941,   947,    953,    967,    971,    977,
				  983,    991,    997,   1009
				};

#define PRECOMPUTED_CUMULATIVE_TOTIENT_COUNT 43

int PrecomputedIndexes[PRECOMPUTED_CUMULATIVE_TOTIENT_COUNT] = 
				{
						1,		10, 	100, 	1000,	5000,	10000,
					20000,	 30000,   40000,   50000,  60000,   70000,
					80000,   90000,  100000,  120000, 140000,  170000,
				   200000,  230000,  260000,  300000, 340000,  380000,
				   420000,  460000,  500000,  540000, 580000,  620000,
				   660000,  700000,  740000,  780000, 820000,  840000,
				   880000,  920000,  960000,  970000, 980000,  990000,
				  1000000
				};

long long PrecompFactCount[PRECOMPUTED_CUMULATIVE_TOTIENT_COUNT] = 
				{
							1,				63,			   6087,  		  608383,		 15200915,		    60794971,
					243180791,	     547143547,       972691431,      1519848527,       2188555011,       2978851639,
				   3890800331,	    4924207659,      6079301507,      8754197331,      11915440063,      17569205355,
				  24317197835,	   32159424339,     41096016235,     54713496967,      70276400759,      87784955879,
				 107238475131,	  128637447559,    151982079351,    177271772471,     204506694419,     233687520819,
				 264813232619,    297884379079,    332901285131,    369862998495,     408770500927,     428953611667,
				 470778807655,    514549986615,    560265984243,    571998834247,     583853779039,     595829589439,
				 607927104783
				};
				
				
int EulerTotientFunction(int Number)
{
	int Totient = 1;
	
	int PrimeIndex = 0;
	
	while (Number > 1)
	{
		int SavedNumber = Number;
		int Power = 0;
		
		int CurrentPrime = PrecomputedPrimes[PrimeIndex];
		
		while ((Number % CurrentPrime) == 0)
		{
			Number = Number / CurrentPrime;
			Power++;	
		}
		
		if (Power > 0)
		{
			Totient *= ((SavedNumber / Number / CurrentPrime) * (CurrentPrime - 1));
		}
		else
		{
			//Check if it is prime 
			if ( (CurrentPrime * CurrentPrime) > Number )	
			{
				Totient *= (Number - 1);
				break;
			}
		}
		PrimeIndex++;
	}
	
	return Totient;
}

long long GetFractionsCountUsingTotientAndPrecomputedTables(int Number)
{
	int LessOrEqualPrecFracIndex = PRECOMPUTED_CUMULATIVE_TOTIENT_COUNT - 1;
	
	while (PrecomputedIndexes[LessOrEqualPrecFracIndex] > Number)
		LessOrEqualPrecFracIndex--;
	
	long long FractionsCount = PrecompFactCount[LessOrEqualPrecFracIndex];
	
	if (Number > PrecomputedIndexes[LessOrEqualPrecFracIndex])
	{
		//Get the nearest precomputed index
		int PrecIndexBefore = PrecomputedIndexes[LessOrEqualPrecFracIndex];
		int PrecIndexAfter = PrecomputedIndexes[LessOrEqualPrecFracIndex + 1];
		
		int TotientsToCalculateBefore = (Number - PrecIndexBefore);
		int TotientsToCalculateAfter  = (PrecIndexAfter - Number);
		
		int CurrentNumber = 0;
		
		if (TotientsToCalculateBefore <= TotientsToCalculateAfter)
		{
			FractionsCount = PrecompFactCount[LessOrEqualPrecFracIndex];
			
			for (CurrentNumber = PrecIndexBefore + 1; CurrentNumber <= Number; CurrentNumber++)
			{
				int CrtEulerTotient = EulerTotientFunction(CurrentNumber);
			
				FractionsCount += (2 * CrtEulerTotient);
			}
		}
		else
		{
			FractionsCount = PrecompFactCount[LessOrEqualPrecFracIndex + 1];
			
			for (CurrentNumber = PrecIndexAfter; CurrentNumber > Number; CurrentNumber--)
			{
				int CrtEulerTotient = EulerTotientFunction(CurrentNumber);
			
				FractionsCount -= (2 * CrtEulerTotient);
			}
		}
				
	}
	
	return FractionsCount;
}

int main()
{	
	FILE* fInput  = NULL;
	FILE* fOutput = NULL;
	
	fInput  = fopen("fractii.in", "r");
	if (fInput == NULL)
		return 0;
	
	fOutput = fopen("fractii.out", "w");
	if (fOutput == NULL)
		return 0;
	
 	int MaxDenominator = 0;
 	fscanf(fInput, "%d", &MaxDenominator);
 	
 	long long FractionsCount = GetFractionsCountUsingTotientAndPrecomputedTables(MaxDenominator);
 	
 	//Because can't write in file long long, use a trick:)
 	long FirstPart = (FractionsCount / SPLIT);
 	long SecondPart = (FractionsCount % SPLIT);
 	
 	if (FirstPart > 0)
 	{
 		fprintf(fOutput, "%ld", FirstPart);
 		
 		char strSecondPart[16];
 		sprintf(strSecondPart, "%09ld", SecondPart);
 		
 		fprintf(fOutput, "%s\n", strSecondPart);
 	}
 	else
 	{
 		fprintf(fOutput, "%ld\n", SecondPart);
 	}
		
	fclose(fInput);
	fclose(fOutput);
	
	return 0;
}