No tag edit access

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-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2017 08:16:31 (c2).

Desktop version, switch to mobile version.

User lists

Name |
---|