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

Вхідні дані

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

Вихідні дані

Для кожного значення n вивести в окремому рядку таку кількість чисел m, що 1 ≤ m ≤ n, НСД(m,n)** ≠ 1 та НСД(m,n) ≠ m.