Magic Triples

Time limit2sMemory limit1024 MB

Summary

Count triples a < b < c up to n where each of the products a*b, a*c, and b*c is a perfect square.

Level: Medium5 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Statement

While Ian and Barley were driving down the highway, Ian suggested that Barley count magic triples to keep himself busy. A triple of positive integers $a$ , $b$ , and $c$ ( $1 \le a < b < c \le n$ ) is called magic if $a \cdot b$ , $a \cdot c$ , and $b \cdot c$ are all squares of positive integers.

Help Barley solve Ian's problem by counting the magic triples.

Input

The only line contains one integer $n$ ( $1 \le n \le 200\,000$ ).

Output

Print one integer, the number of magic triples.

Hint

For $n = 10$ , the only magic triple is $a = 1$ , $b = 4$ , $c = 9$ .

For $n = 20$ , the magic triples are:

$a = 1$ , $b = 4$ , $c = 9$
$a = 1$ , $b = 4$ , $c = 16$
$a = 1$ , $b = 9$ , $c = 16$
$a = 4$ , $b = 9$ , $c = 16$
$a = 2$ , $b = 8$ , $c = 18$

Examples2

Example 1
Input
```
10
```
Expected output
```
1
```
Example 2
Input
```
20
```
Expected output
```
5
```