서로소 그래프

시간 제한1초메모리 제한512 MB

요약

1부터 N까지의 정수 중 서로소인 두 수의 쌍의 개수를 세어 그래프의 간선 수를 구한다.

문제

우석이는 심심할 때마다 그래프를 그린다. 우석이는 매달 새로운 그래프를 그리는데, 이번 달에는 서로소 그래프를 그린다.

서로소 그래프는 $1$ 부터 $N$ 까지의 번호를 가진 $N$ 개의 정점으로 이루어져 있으며, 서로 다른 두 정점의 번호가 서로소일 때만 두 정점이 간선 하나로 직접 연결되어 있다.

우석이는 간선을 얼마나 많이 그려야할지 궁금해졌다. 정점의 개수 $N$ 이 주어질 때, 만들어야 하는 간선의 개수를 알려주자.

첫째 줄에 그래프의 정점 개수 $N$ 이 주어진다.

우석이가 그려야하는 간선의 수를 출력한다.