get_string(String) :-
  current_input(Input),
  read_string(Input, ' \n', '', _, String).
 
get_number(Number) :-
  get_string(String),
  number_string(Number, String).

gcd(0, B, B).
gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).

solve(N,N,N,N,N) :- !.
solve(I,N,N,N,Ans) :- !,
  gcd(I,N,G), 
  Next is I + 1, 
  solve(Next,1,1,N,R), 
  Ans is G + R.
  %write(I),write(' '),write(N),write(' '),write(N),write(' '),writeln(Ans).
solve(I,J,N,N,Ans) :- !,
  gcd(I,J,G1), 
  gcd(G1,N,G2),
  Next is J + 1, 
  solve(I,Next,1,N,R), 
  Ans is G2 + R.
  %write(I),write(' '),write(J),write(' '),write(N),write(' '),writeln(Ans).
solve(I,J,K,N,Ans) :- 
  gcd(I,J,G1), 
  gcd(G1,K,G2),
  Next is K + 1,
  solve(I,J,Next,N,R), 
  Ans is G2 + R.
  %write(I),write(' '),write(J),write(' '),write(K),write(' '),writeln(Ans).

main :-
  get_number(N),
  solve(1,1,1,N,Ans),
  writeln(Ans).