p02713 AtCoder Beginner Contest 162 - Sum of gcd of Tuples (Easy)
Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

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

Constraints

* 1 \leq K \leq 200
* K is an integer.

Input

Input is given from Standard Input in the following format:


K


Output

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

Examples

Input

2


Output

9


Input

200


Output

10813692
```python
import math
K=int(input())
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans+=math.gcd(math.gcd(i,j),k)
print(ans)
```