Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Dado $N$, un número entero positivo, cuántos números enteros positivos menores que $N$ hay que son primos relativos con $N$? Dos números enteros $a$ y $b$ son primos relativos si no hay enteros $x \gt 1$, $y \gt 0$, $z \gt 0$ tal que $b=xz$  y $a=xy$.

Input

Cada entrada tiene múltiples casos de prueba. Por cada caso de prueba en una línea hay un entero $N \le 10^{10}$. Una línea con un entero $0$ marca el último caso de prueba.

Output

Por cada caso de prueba se imprime la respuesta.

Sample test(s)