e-olymp

Теория чисел

Математики - любопытная порода людей. Особенно в области теории чисел. Они проводят большую часть своего времени, думая о различных свойствах чисел. Альберт Мейер, специалист по теории чисел, пытается открыть для себя интересную последовательность натуральных чисел. Он считает, что последовательность i1, i2, i3,... in, в которой in равно количеству таких чисел m, что 1mn, НОД(m, n) ≠ 1 и НОД(m, n) ≠ m, является довольно интересной. Через НОД здесь обозначен "Наибольший Общий Делитель". Он обратился к Вам как к опытному программисту с просьбой вычислить несколько чисел этой последовательности.

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

Каждая строка содержит одно натуральное число n (0 < n < 231).

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

Для каждого значения n вывести в отдельной строке количество таких чисел m, что 1mn, НОД(m, n) ≠ 1 и НОД(m, n) ≠ m.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
1
2
6
2147000000
Выходные данные #1
0
0
1
1340599805