Acquainted Through Friends

The theory that six handshakes are enough to connect everyone in the world is well known. Consider a situation where every person is connected to every other through a chain of acquaintances.

There are $N$ people who do not know each other. They are numbered from $1$ to $N$. Any two of them can share a meal and become friends. The price of the meal is set as follows.

• If the two numbers are coprime, the price is the larger of the two numbers. Two numbers are coprime when their only common divisor is 1.
• If the two numbers are not coprime, the price is the greatest common divisor of the two numbers.

A friend of a friend, or a friend of a friend of a friend, is called an 'acquaintance through friends'. Draw each friendship as an edge in a graph. If a path exists from vertex $u$ to vertex $v$, then $u$ and $v$ are acquainted through friends. If $u$ and $v$ are friends, a path exists between them, so they are also acquainted through friends.

The $N$ people become friends so that every pair is acquainted through friends. Write a program that finds the minimum total price of the meals needed to achieve this.

The input is given as follows.

$N$

On the first line, print the minimum total cost.

• $2\leq N\leq 1\,000\,000$