Cidoai的数论求和
题号：NC276581
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

求 \sum_{i=1}^n\sum_{j=1}^{n}\sum_{k=1}^n[\gcd(i,j,k)=1][ij=k(i-j)] 其中 \gcd 表示最大公约数，[] 表示艾弗森括号，若括号内命题为真，它的值为 1，否则为 0。

输入描述:

一行一个正整数 n。

输出描述:

一行一个整数表示答案。
示例1

输入

复制 
10

输出

复制 
3
示例2

输入

复制 
1000000

输出

复制 
421389
示例3

输入

复制 
10000000000

输出

复制 
4213829685

备注:

n \le 10^{13}