C. You can't just take and divide
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anatoly and Antitoly met on a forum about numerical injustice.

It turned out that besides their love for mathematics, they have many differences.

For example, Anatoly always strives for a fair distribution of resources and is not afraid of difficulties.

Antitoly, on the other hand, finds pleasure in the unfair distribution of resources and seeks simplicity in everything.

At the moment, Antitoly is developing his model of an ideal society, defined by the parameter $$$n$$$.

To complete his model, Antitoly needs to compute exactly one quantity — the number of integers $$$x$$$ in the range from $$$1$$$ to $$$n$$$ such that:

  • the number $$$x$$$ itself is odd (even numbers are too easy to divide in half, Antitoly does not like them);
  • the number of divisors of $$$x$$$ is odd and prime.
Input

The first line contains an integer odd number $$$n$$$ $$$(3 \le n \le 11^{13})$$$ — the parameter of the ideal society in Antitoly's model.

Output

Output a single integer $$$R$$$ $$$(0 \le R \le n)$$$ — the number of integers $$$x$$$ in the range from $$$1$$$ to $$$n$$$ such that:

  • the number $$$x$$$ itself is odd;
  • the number of divisors of $$$x$$$ is odd and prime.
Examples
Input
3
Output
0
Input
5
Output
0
Input
9
Output
1
Input
111
Output
4
Input
9753113579
Output
9563
Note

Definition A positive integer is called prime if it has exactly two distinct divisors.

For example, the numbers $$$3$$$, $$$17$$$, and $$$59$$$ are prime, while the numbers $$$1$$$ ($$$1$$$ divisor), $$$9$$$ ($$$3$$$ divisors), $$$30$$$ ($$$8$$$ divisors), and $$$111$$$ ($$$4$$$ divisors) are not prime.

First test example

Consider each of the numbers not exceeding $$$3$$$:

  • $$$1$$$ has $$$1$$$ divisor — the number of divisors is odd, but not prime.
  • $$$2$$$ has $$$2$$$ divisors — the number itself is even, so it is not of interest.
  • $$$3$$$ has $$$2$$$ divisors — the number of divisors is prime, but even.

Accordingly, there are no suitable numbers for Antitoly.

Second test example

Compared to the first test, two numbers are added:

  • $$$4$$$ has $$$3$$$ divisors — the number of divisors is odd and prime, but the number itself is even.
  • $$$5$$$ has $$$2$$$ divisors — the number of divisors is prime, but even.

So far, there are still no suitable numbers for Antitoly.

Third test example

Compared to the second test, four numbers are added:

  • $$$6$$$ and $$$8$$$ — even numbers, not of interest.
  • $$$7$$$ has $$$2$$$ divisors — the number of divisors is prime, but even.
  • $$$9$$$ has $$$3$$$ divisors — the number of divisors is both prime and odd.