f(n)

This time I need you to calculate the f(n) . (3<=n<=1000000)

f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n).
Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])
C[n][k] means the number of way to choose k things from n some things.
gcd(a,b) means the greatest common divisor of a and b.

There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF.

For each test case:
The output consists of one line with one integer f(n).

3
26983

3
37556486

ECJTU 2009 Spring Contest