A triplet $(p1,p2,p3)$ where $p1,p2,p3$ are primes (not necessarily distinct) is called special if $p1+p2+p3$ divides $p1*p2*p3$. Find the number of triplets such that each prime of the triplet is not greater than $N$. Two triplets are considered to be different if the element at any one of the positions (first, second, third) is different in the second one.

Input format

The first line of the input consists of an integer $N$.

Output format

Print the answer in a single line.

Constraints

$1<=N<=10^6$