B. Вычитание делителя
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано целое число $$$n$$$. К нему применяется следующий алгоритм:

  1. если $$$n = 0$$$, то завершить алгоритм;
  2. найти наименьший простой делитель $$$d$$$ числа $$$n$$$;
  3. вычесть $$$d$$$ из $$$n$$$ и перейти к шагу $$$1$$$.

Определите количество вычитаний, которые совершит алгоритм.

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

В единственной строке записано одно целое число $$$n$$$ ($$$2 \le n \le 10^{10}$$$).

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

Выведите единственное целое число — количество вычитаний, которые совершит алгоритм.

Примеры
Входные данные
5
Выходные данные
1
Входные данные
4
Выходные данные
2
Примечание

В первом примере $$$5$$$ — это наименьший простой делитель, поэтому он сразу вычтется, приведя число к $$$0$$$.

Во втором примере $$$2$$$ — наименьший простой делитель на обоих шагах.