#10179Irreducible Basic Fractions

★

時間限制：2000 毫秒記憶體限制：64 MB

A fraction m/n is basic if 0 ≤ m < n and it is irreducible if gcd(m, n) = 1. Given a positive integer n, in this problem you are required to find out the number of irreducible basic fractions with denominator n.

For example, the set of all basic fractions with denominator 12, before reduction to lowest terms, is

Reduction yields

Hence there are only the following 4 irreducible basic fractions with denominator 12

Input

Each line of the input contains a positive integer n (< 1000000000) and the input terminates with a value 0 for n (do not process this terminating value).

Output

For each n in the input print a line containing the number of irreducible basic fractions with denominator n.

範例輸入 1

範例輸出 1

4
41088
7251444

Pro 專屬功能：查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.

\frac{0}{12}, \frac{1}{12}, \frac{2}{12}, \frac{3}{12}, \frac{4}{12}, \frac{5}{12}, \frac{6}{12}, \frac{7}{12}, \frac{8}{12}, \frac{9}{12}, \frac{10}{12}, \frac{11}{12}

\frac{0}{12}, \frac{1}{12}, \frac{1}{6}, \frac{1}{4}, \frac{1}{3}, \frac{5}{12}, \frac{1}{2}, \frac{7}{12}, \frac{2}{3}, \frac{3}{4}, \frac{5}{6}, \frac{11}{12}

\frac{1}{12}, \frac{5}{12}, \frac{7}{12}, \frac{11}{12}