P4844 LJJ Loves Counting.

For the solution, please see 。

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.

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

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

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