Задача M. Функция Эйлера - 1

Автор:Эйлер   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Необходимо вычислить функцию Эйлера для натурального числа N.

Формат входного файла

Входной файл содержит одно целое положительное число N.

Формат выходного файла

Выходной файл должен содержать одно целое положительно число - значение функции Эйлера для N.

Ограничения

1 ≤ N ≤ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
4
2
9
6

0.102s 0.019s 13