경로

양의 정수 n이 주어진다. 정점 1, 2, ..., n로 이루어진 그래프를 다음과 같이 만들자. 일 때, 그리고 그럴 때에만 정점 u와 v 사이에 간선이 있다. u와 v 사이의 최단 거리를 d(u, v)라 하고, 둘 사이에 경로가 없으면 0이라 하자. 모든 1 ≤ u < v ≤ n에 대해 d(u, v) 값의 합을 구한다.

두 양의 정수의 gcd(최대공약수)는 두 정수를 모두 나누는 양의 정수 중 최댓값이다.

하나의 정수 n (1 ≤ n ≤ 107)이 주어진다.

모든 1 ≤ u < v ≤ n에 대해 d(u, v)의 합을 출력한다.

첫 번째 예제의 모든 최단 경로는 다음과 같다.

그 밖의 정점 쌍 사이에는 경로가 없다.

거리의 총합은 2 + 1 + 1 + 2 + 1 + 1 = 8이다.