Background

For the solution, please see https://www.cnblogs.com/Blog-of-Eden/p/9367521.html。

Problem Description

Once when reading a magazine, PJY saw a problem:

Find all positive integer triples $(a,b,c)$ such that $a,b,c \leq n$, the greatest common divisor of the three numbers $\bold{a,b,c}$ is $\bold{1}$, and $\bold{\frac{1}{a}+\frac{1}{b}=\frac{1}{c}}$.

PJY thought this problem was too easy, so he threw it to LJJ, who loves counting, and added the Constraints $\bold{n \leq 10^{12}}$, asking LJJ to count how many triples $\bold{(a,b,c)}$ satisfy the conditions
(note that when $a \not= b$, $(a,b,c)$ and $(b,a,c)$ are different triples and should be counted twice).

Halfway through counting, LJJ found that the number was too large, so he passed the problem to you. Please output this number.

Input Format

Only one line: a positive integer $n(n\leq 10^{12})$。

Output Format

Only one line: an integer, representing the number of triples $(a,b,c)$ that satisfy the conditions.

10

3

100

43

100000

42139

Hint

For $20\%$ of the testdata, $n \leq 2 \times 10^{3}$。

For $40\%$ of the testdata, $n \leq 10^{5}$。

For $60\%$ of the testdata, $n \leq 10^{7}$。

For $80\%$ of the testdata, $n \leq 10^{9}$。

For $100\%$ of the testdata, $n \leq 10^{12}$。

Translated by ChatGPT 5