题目背景

题解请查看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