Educational Codeforces Round 12 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

math

number theory

sortings

two pointers

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Four Divisors

time limit per test

10 secondsmemory limit per test

768 megabytesinput

standard inputoutput

standard outputIf an integer *a* is divisible by another integer *b*, then *b* is called the divisor of *a*.

For example: 12 has positive 6 divisors. They are 1, 2, 3, 4, 6 and 12.

Let’s define a function *D*(*n*) — number of integers between 1 and *n* (inclusive) which has exactly four positive divisors.

Between 1 and 10 only the integers 6, 8 and 10 has exactly four positive divisors. So, *D*(10) = 3.

You are given an integer *n*. You have to calculate *D*(*n*).

Input

The only line contains integer *n* (1 ≤ *n* ≤ 10^{11}) — the parameter from the problem statement.

Output

Print the only integer *c* — the number of integers between 1 and *n* with exactly four divisors.

Examples

Input

10

Output

3

Input

20

Output

5

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2024 17:27:53 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|