#include <iostream>
#include <fstream>
using namespace std;


int cmmdc(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}


int main() {
    int N, P, Q, nrFractii;

    // 1. Citire N
    ifstream fin ("fractii.in");
    fin >> N;
    fin.close();
    if (N < 1 || N > 1000000) {
        cout << "N trebuie sa fie cuprins intre 1 si 1 milion.";
        return 1;
    }

    // 2. Determinare fracții ireductibile
    nrFractii = 0;
    for (P = 1; P <= N; P++) {
        for (Q = 1; Q <= N; Q++) {
            if (cmmdc(P,Q) == 1)
                nrFractii++;
        }
    }

    // 3. Printarea numărului
    ofstream fout ("fractii.out");
    fout << "Sunt " << nrFractii << " fractii ireductibile.";
    fout.close();

    return 0;
}