영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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 · 3 · 4 and 336 = 6 · 7 · 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 ≤ N ≤ 10^9), whose meaning is described above.
Output
Print an integer: the number of integers less than N that are triple numbers.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 20 | N ≤ 30 |
| 2 | 20 | N ≤ 80 |
| 3 | 20 | N ≤ 1000 |
| 4 | 20 | N ≤ 10^5 |
| 5 | 20 | No additional constraints. |
예제
예제 1
30
2
예제 2
24
1
예제 3
1234
9