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

ifstream f("fractii.in");
ofstream g("fractii.out");
void addF(short tata[],int nr,int prim)
{
    if( tata[nr] == 0) tata[nr] = prim;
}
int main()
{
    int n,k,i;
    long s;
    bool v[1000001];
    short tata[1000001] = {0};
    int sume[1000001] = {0};
    f>>n;
    for(i = 1;i <= n;i++) v[i] = true; /* initializare */
    k = 2;
    while(k<=n)
    {
        sume[k] = k-1; /* k-1 fractii ireductibile de tipul i / k, unde i < k */
        v[k] = false;
        for(i=2*k;i<=n;i += k)
        {
            v[i] = false;
            addF(tata,i,k); //adauga numai daca nu are deja
            cout<<k<<" "<<i<<endl;
        }
        while(v[k] == false && k<=n)
        {
            cout<<k<<" "<<k<<endl;
            k++;
        }
    }
    for(i=2;i<=n;i++)
        if(sume[i] == 0) // numarul nu este prim, deci are "tata"
        {
            short aux;
            int j,auxN,
                pow = 0,
                a = i;
            do{
                pow++; //numara ordinul puterii
                aux = tata[a]; // cel mai mic divizor in afara de 1
                a = a/aux; // impartim pe a la acel divizor
            }while(aux == tata[a]);
            auxN = 1;
            for(j=1;j<=pow;j++) auxN *= int(aux);
            cout<<"coef pt "<<i<<"este "<<auxN<<endl;
            if(auxN*aux == i)
                sume[i] = i*(aux-1)/aux; /* formula */
            else
                sume[i] = sume[auxN]*sume[i/auxN];
        }
    s=1; /* prima fractie 1/1 */
    for(i=2;i<=n;i++) s += 2*sume[i];
    g<<s;
    f.close();
    g.close();
    return 0;
}