Coprime

Interview

Time limit1sMemory limit128 MB

Summary

For each n up to 1e9, count how many positive integers less than n share no common factor with n, handling several test cases until a 0.

Level: Medium5 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Problem

Given a positive integer $n$ , write a program that counts how many positive integers smaller than $n$ are coprime with $n$ .

Two integers $a$ and $b$ are coprime when there is no integer $x > 1$ together with positive integers $y$ and $z$ such that $a = xy$ and $b = xz$ . In other words, their only common divisor is $1$ .

Input

The input consists of several test cases. Each test case is a single line containing one integer $n$ with $1 \le n \le 1{,}000{,}000{,}000$ .

The last line of the input contains $0$ and is not processed.

Output

For each test case, print on its own line the number of positive integers smaller than $n$ that are coprime with $n$ .

Examples1

Example 1
Input
```
7
12
0
```
Expected output
```
6
4
```