Problem Description

PJY came across a problem in a magazine:

Find all positive integer triplets {a, b, c} such that a, b, c ≤ n, the greatest common divisor of a, b, and c is 1, and 1/a + 1/b = 1/c.

PJY found this problem too easy and passed it on to LJJ, who loves counting. PJY also added the constraint n ≤ 1e12 and asked LJJ to count the number of such triplets {a, b, c}.

Note that when a is not equal to b, {a, b, c} and {b, a, c} are considered different triplets and should be counted twice.

LJJ got overwhelmed by the large number of triplets and passed the problem to you. Please output the count of such triplets.

Input Format

The input consists of a single line containing a positive integer n (n ≤ 1e12).

Output Format

The output consists of a single line containing an integer, representing the number of triplets {a, b, c} that satisfy the conditions.

Sample Input and Output

Sample Input #1

10

Sample Output #1

3

Sample Input #2

100

Sample Output #2

43

Sample Input #3

100000

Sample Output #3

42139

Notes/Hints

20%: n ≤ 2000

40%: n ≤ 100000

60%: n ≤ 10000000

80%: n ≤ 1e9

100%: n ≤ 1e12

见题面 Input 部分

见题面 Output 部分