C. Нельзя просто так взять и поделить
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Анатолий и Антитолий пересеклись на форуме по проблемам числовой несправедливости.

Выяснилось, что кроме их любви к математике, у них очень много различий.

Например, Анатолий всегда стремится к честному распределению благ и не боится сложностей.

Антитолий же находит удовольствие в несправедливом распределении ресурсов, а также стремится к простоте во всём.

В данный момент Антитолий разрабатывает свою модель идеального общества, заданного параметром $$$n$$$.

Для завершения Антитолию осталось вычислить ровно одну величину — количество целых чисел $$$x$$$ в промежутке от $$$1$$$ до $$$n$$$ таких, что:

  • само число $$$x$$$ является нечётным (чётные числа слишком легко разделить пополам, Антитолию они не нравятся);
  • количество делителей числа $$$x$$$ является нечётным и простым.
Входные данные

В первой строке дано целое нечётное число $$$n$$$ $$$(3 \le n \le 11^{13})$$$ — параметр идеального общества в модели Антитолия.

Выходные данные

Выведите единственное целое число $$$R$$$ $$$(0 \le R \le n)$$$ — количество целых чисел $$$x$$$ в промежутке от $$$1$$$ до $$$n$$$ таких, что:

  • само число $$$x$$$ является нечётным;
  • количество делителей числа $$$x$$$ является нечётным и простым.
Примеры
Входные данные
3
Выходные данные
0
Входные данные
5
Выходные данные
0
Входные данные
9
Выходные данные
1
Входные данные
111
Выходные данные
4
Входные данные
9753113579
Выходные данные
9563
Примечание

Определение Целое положительное число называется простым, если у него ровно два различных делителя.

Например, числа $$$3$$$, $$$17$$$ и $$$59$$$ являются простыми, а числа $$$1$$$ ($$$1$$$ делитель), $$$9$$$ ($$$3$$$ делителя), $$$30$$$ ($$$8$$$ делителей) и $$$111$$$ ($$$4$$$ делителя) простыми не являются.

Первый тестовый пример

Рассмотрим каждое из чисел, не превышающих $$$3$$$:

  • $$$1$$$ имеет $$$1$$$ делитель — количество делителей нечётное, но не простое.
  • $$$2$$$ имеет $$$2$$$ делителя — само число чётное, поэтому не интересует.
  • $$$3$$$ имеет $$$2$$$ делителя — количество делителей простое, но чётное.

Соответственно, нет ни одного подходящего Антитолию чисел.

Второй тестовый пример

По сравнению с первым тестом добавляются два числа:

  • $$$4$$$ имеет $$$3$$$ делителя — количество делителей нечётное и простое, но само число чётное.
  • $$$5$$$ имеет $$$2$$$ делителя — количество делителей простое, но чётное.

До сих пор нет подходящих Антитолию чисел.

Третий тестовый пример

По сравнению со вторым тестом добавляются четыре числа:

  • $$$6$$$ и $$$8$$$ — чётные числа, не интересуют.
  • $$$7$$$ имеет $$$2$$$ делителя — количество делителей простое, но чётное.
  • $$$9$$$ имеет $$$3$$$ делителя — количество делителей и простое, и нечётное.