A. Коровки и первообразные корни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Коровки только что узнали, что такое первообразный корень! Вам дано простое число p, первообразный корень — целое число x (1 ≤ x < p), такое, что ни одно из целых чисел x - 1, x2 - 1, ..., xp - 2 - 1 не делится на p, при этом число xp - 1 - 1 делится на p.

К сожалению, на вычисление первообразных корней уходит много времени, так что коровкам нужна Ваша помощь. Вам дано простое число p, помогите коровкам найти количество первообразных корней .

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

Во входных данных содержится единственная строка, в которой записано целое число p (2 ≤ p < 2000). Гарантируется, что p является простым числом.

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

В единственной строке выведите количество первообразных корней .

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

Единственный первообразный корень 2.

Первообразные корни 2 и 3.