eolymp
bolt
Try our new interface for solving problems
Problems

Again irreducible

Again irreducible

Time limit 1 second
Memory limit 128 MiB

The fraction m / n is called regular irreducible, if 0 < m < n and GCD(m, n) = 1. Find the number of regular irreducible fractions with the denominator n.

Input data

Each line is a separate test case that contains one integer n~(n < 10^9). The last line contains 0 and is not processed. The number of test cases is no more than 100.

Output data

For each value of n print in a separate line the answer to the problem.

Examples

Input example #1
12
123456
7654321
0
Output example #1
4
41088
7251444