Counting Reciprocal Equation Triples

Given a positive integer n (with n ≤ 10¹²), count the number of ordered triples of positive integers (a, b, c) such that:

• a, b, c ≤ n
• gcd(a, b, c) = 1
• The equation $$\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$$ holds.

Note that when a ≠ b, the triple (a, b, c) is considered different from (b, a, c).

Hint: It can be shown that the equation can be rewritten as $$ (a-c)(b-c)=c^2. $$ For a given positive integer c, any pair of positive divisors \(x, y\) satisfying $$ x\,y= c^2 $$ leads to a solution by taking \(a = c+x\) and \(b = c+y\). However, the constraints a, b ≤ n and the condition gcd(a, b, c)=1 force that only divisors of a very specific form are allowed. In fact, one may prove that for every prime factor \(p\) of c (with \(c=p^e\)), the allowed divisor must have an exponent equal either to \(0\) or \(2e\) so that the contribution of c in the triple is eliminated. Consequently, if \(\omega(c)\) denotes the number of distinct prime factors of c, then for those values of c where the extra conditions are satisfied, there are exactly \(2^{\omega(c)}\) valid pairs \((x,y)\>.

One may further show that all valid solutions occur only when \(c\) satisfies $$ c^2+c\le n, $$ so if we define $$ T=\left\lfloor \frac{\sqrt{4n+1}-1}{2} \right\rfloor, $$ then the final answer is $$ \sum_{c=1}^{T}2^{\omega(c)}. $$

inputFormat

The input consists of a single line containing a positive integer n (n ≤ 10¹²).

For example:

20

outputFormat

Output a single integer — the number of triples (a, b, c) satisfying the conditions.

sample

6

3