LJJ爱数数

题解请查看[https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)

PJY某次翻阅杂志时，看到一道题： 求出所有的**正整数**三元组{a,b,c}，满足a,b,c<=n，**a,b,c三个数的最大公约数为1**，且**1/a+1/b=1/c**。 PJY嫌这道题太水，于是把它甩给了爱数数的LJJ，并加上了数据范围**n<=1e12**，让LJJ数出**有多少组满足条件的三元组{a,b,c}** （注意当a不等于b时，{a,b,c}和{b,a,c}是不同的三元组，要算两次） LJJ数到一半，发现这个数量太大了，于是他把问题抛给了你。请你输出这个数量。

输入仅一行：一个正整数n（n<=1e12）

输出仅一行：一个整数，表示满足条件的三元组{a,b,c}的数量

10

3

100

43

100000

42139

20%：n<=2000 40%：n<=100000 60%：n<=10000000 80%：n<=1e9 100%：n<=1e12