题目背景

题解请查看 https://www.cnblogs.com/Blog-of-Eden/p/9367521.html。

题目描述

PJY 某次翻阅杂志时，看到一道题：

求出所有的 正整数 三元组 $(a,b,c)$，满足 $a,b,c \leq n$，$\bold{a,b,c}$ 三个数的最大公约数为 $\bold{1}$，且 $\bold{\frac{1}{a}+\frac{1}{b}=\frac{1}{c}}$。

PJY 嫌这道题太水，于是把它甩给了爱数数的 LJJ，并加上了数据范围 $\bold{n \leq 10^{12}}$，让 LJJ 数出 有多少组满足条件的三元组 $\bold{(a,b,c)}$ （注意当 $a \not= b$ 时，$(a,b,c)$ 和 $(b,a,c)$ 是不同的三元组，要算两次）

LJJ 数到一半，发现这个数量太大了，于是他把问题抛给了你。请你输出这个数量。

输入格式

输入仅一行：一个正整数 $n(n\leq 10^{12})$。

输出格式

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

10

3

100

43

100000

42139

提示

对于 $20\%$ 的数据，$n \leq 2 \times 10^{3}$。

对于 $40\%$ 的数据，$n \leq 10^{5}$。

对于 $60\%$ 的数据，$n \leq 10^{7}$。

对于 $80\%$ 的数据，$n \leq 10^{9}$。

对于 $100\%$ 的数据，$n \leq 10^{12}$。