/ WHOJ / 题库 /

GCD 的和

GCD 的和

描述

给定nn,求出:
i=1nj=1nk=1ngcd(i,j,k)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}\gcd(i,j,k)

格式

输入格式

输入一个整数 nn

输出格式

输出一个整数,表示答案。

样例1

输入样例1

输出样例1

样例解释

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)=1+1+1+1+1+1+1+2=9\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)=1+1+1+1+1+1+1+2=9。

限制

对于100100%的数据,1n2001≤n≤200