Hide

Problem H
Three in a Row

Languages en sv

The mathematician Lenore Oljer has done so much math that she has grown tired of prime numbers. She has now started studying so-called “nice triplets”. It’s very easy to create a nice triplet. Start with an integer $a$ greater than zero and then create the triplet $(a, a+1, a+2)$. All triplets created in this way are considered nice. Some examples of nice triplets are $(4,5,6)$ and $(15,16,17)$.

To learn more about nice triplets, Lenore wants to find out how many numbers can be written as the product of all the numbers in a nice triplet. She calls these numbers “triple numbers”. Some examples of triple numbers are $24=2 \cdot 3 \cdot 4$ and $336 = 6 \cdot 7 \cdot 8$. Lenore now wants to know how many triple numbers there are that are less than the given number $N$.

Write a program that takes the number $N$ as input and prints out how many numbers less than $N$ that are triple numbers.

Input

The first and only line of the input contains the integer $N$ ($1 \le N \le 10^9$), whose meaning is described above.

Output

Print an integer: the number of integers less than $N$ that are triple numbers.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Group

Point value

Constraints

$1$

$20$

$N \leq 30$

$2$

$20$

$N \leq 80$

$3$

$20$

$N \leq 1000$

$4$

$20$

$N \leq 10^5$

$5$

$20$

No additional constraints.

Sample Input 1 Sample Output 1
30
2
Sample Input 2 Sample Output 2
24
1
Sample Input 3 Sample Output 3
1234
9

Please log in to submit a solution to this problem

Log in