25921번 - 건너 아는 사이

문제

여섯 다리만 건너면 전 세계의 모든 사람을 알게 된다는 이론이 있다. 이렇게 모든 사람이 여러 다리를 건너 알게 된 상황을 떠올려보자.

서로 모르는 $N$명의 사람이 있다. 이들은 각각 1ドル$번부터 $N$번까지 번호가 매겨져 있다. 이들 중 둘은 함께 식사를 하여 서로 친구가 될 수 있다. 음식의 가격은 다음과 같이 정해진다.

• 두 사람의 번호가 서로소일 때, 두 번호 중 큰 값이다. 서로소란 두 수 사이에 1 이외의 공약수가 없음을 의미한다.
• 두 사람의 번호가 서로소가 아닐 때, 두 번호의 최대공약수이다.

'친구의 친구', '친구의 친구의 친구' 등을 '건너 아는 사이'라고 한다. 즉 친구 사이인 두 사람을 모두 연결해 그래프로 나타낼 때, $u$번 정점에서 $v$번 정점으로 가는 경로가 존재한다면 $u$번과 $v$번은 '건너 아는 사이'이다. $u$와 $v$가 친구일 때도 경로가 존재하므로, 친구 사이인 두 사람도 '건너 아는 사이'이다.

$N$명의 사람은 서로 친구가 되어 결국 모든 쌍의 사람이 '건너 아는 사이'가 되었다. 이들은 음식의 가격의 합이 최소가 되도록 서로 '건너 아는 사이'가 되었을 때, 그 가격의 합을 구하는 프로그램을 작성하시오.

입력

입력은 아래와 같이 주어진다.

출력

첫째 줄에 비용의 최솟값을 출력한다.

제한

• 2ドル\leq N\leq1,000円,000円$

힌트