e-olymp
Змагання

Azerbaijan Programming Olympiad - 2nd Stage preparation

Теорія чисел

Математики - цікава порода людей. Особливо в галузі теорії чисел. Вони проводять більшу частину свого часу, думаючи про різні властивості чисел. Альберт Мейєр, фахівець з теорії чисел, намагається відкрити для себе цікаву послідовність натуральних чисел. Він вважає, що послідовність 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