Feather Communication

Madeline observes that while she breathes, a feather stops at several magical positions. The magic value at the i-th stop (with stops numbered from 1) is given by the formula $$ (i+1)^2-1 $$, which can be simplified to $$ i(i+2) $$. To harness the feather's power for flight, she must "communicate" all these stops. The energy required to directly communicate between two stops is equal to the \(\gcd\) (greatest common divisor) of their magic values.

This problem is equivalent to connecting all stops (nodes) with edges weighted by the \(\gcd\) of their magic values. In other words, you are asked to choose a set of \(n-1\) connections (forming a spanning tree) so that the total energy cost is minimized.

Input: A single integer \(n\) representing the number of stops. (If \(n=1\), no connection is required.)

Output: A single integer, the minimum total energy required to connect all the stops.

inputFormat

The input consists of one line containing a single integer \(n\) (\(1 \le n \le 10^4\), for example) which denotes the number of stops.

outputFormat

Output a single integer, which is the minimum energy required to connect all the stops.

sample

1

0