#abc162c. [abc162_c]Sum of gcd of Tuples (Easy)

[abc162_c]Sum of gcd of Tuples (Easy)

Problem Statement

Find displaystylesuma=1Ksumb=1Ksumc=1Kgcd(a,b,c)\\displaystyle{\\sum_{a=1}^{K}\\sum_{b=1}^{K}\\sum_{c=1}^{K} \\gcd(a,b,c)}.

Here gcd(a,b,c)\\gcd(a,b,c) denotes the greatest common divisor of aa, bb, and cc.

Constraints

  • 1leqKleq2001 \\leq K \\leq 200
  • KK is an integer.

Input

Input is given from Standard Input in the following format:

KK

Output

Print the value of displaystylesuma=1Ksumb=1Ksumc=1Kgcd(a,b,c)\\displaystyle{\\sum_{a=1}^{K}\\sum_{b=1}^{K}\\sum_{c=1}^{K} \\gcd(a,b,c)}.


Sample Input 1

Sample Output 1

gcd(1,1,1)+gcd(1,1,2)+gcd(1,2,1)+gcd(1,2,2)\\gcd(1,1,1)+\\gcd(1,1,2)+\\gcd(1,2,1)+\\gcd(1,2,2) +gcd(2,1,1)+gcd(2,1,2)+gcd(2,2,1)+gcd(2,2,2)+\\gcd(2,1,1)+\\gcd(2,1,2)+\\gcd(2,2,1)+\\gcd(2,2,2) 1ˉ+1+1+1+1+1+1+2=9\=1+1+1+1+1+1+1+2=9

Thus, the answer is 99.


Sample Input 2

200

Sample Output 2

10813692