U119598 福利题

（原 idea 来自 [@return20071007](https://www.luogu.com.cn/user/250637)） 屑题不敢丢gks，就放这了。 福利题？魔怔推式子题！

给定 $n$，求 $$ \begin{aligned} \sum_{x=1}^{n}\sum_{y=1}^{n}\sum_{z=1}^{n}lcm( &\frac{lcm(x,z)gcd(y,z)}{gcd(x,y)}, \frac{lcm(y,x)gcd(z,x)}{gcd(y,z)}, \frac{lcm(z,y)gcd(x,y)}{gcd(z,x)},\cr &\frac{lcm(x,z)gcd(x,y)}{gcd(y,z)}, \frac{lcm(y,x)gcd(y,z)}{gcd(z,x)}, \frac{lcm(z,y)gcd(z,x)}{gcd(x,y)} ) \end{aligned} $$

一行一个整数 $n$。

一个整数表示答案。

$1\le n\le 10^6$ 保证暴力有分。 保证输出样例有分。 其实福利是有的，在题目附件里（（（ 2020/10/18：福利附件有更新！！！ 要领福利的好歹输出个样例再走吧。 [$O(n)$ 做法题解](https://www.cnblogs.com/zkyJuruo/articles/13717792.html) by 神 [zhoukangyang](https://www.luogu.com.cn/user/173660) sto [zhoukangyang](https://www.luogu.com.cn/user/173660) orz