A T-prime is the square of a prime number. Count the T-primes not greater than \(n\).

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 10^12\)

Output

Print the required count.

Example

Input

70693043583

Output

23302