Коровки только что узнали, что такое первообразный корень! Вам дано простое число p, первообразный корень 
— целое число x (1 ≤ x < p), такое, что ни одно из целых чисел x - 1, x2 - 1, ..., xp - 2 - 1 не делится на p, при этом число xp - 1 - 1 делится на p.
К сожалению, на вычисление первообразных корней уходит много времени, так что коровкам нужна Ваша помощь. Вам дано простое число p, помогите коровкам найти количество первообразных корней .
Выходные данные
В единственной строке выведите количество первообразных корней .
Примечание
Единственный первообразный корень 
— 2.
Первообразные корни 
— 2 и 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
1
|
|
2
|
5
|
2
|