Problem E
Relatives

/problems/relatives/file/statement/en/img-0001.jpg

Given

n

, a positive integer, how many positive integers less than

n

are relatively prime to

n

? Two integers

a

and

b

are relatively prime if there are no integers

x \geq 2, y \geq 1, z \geq 1

such that

a = x y

and

b = x z

.

Input

There up to $10$ test cases. For each test case, standard input contains a line with $1 \leq n \leq 1 000 000 000$ . A line containing $0$ follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input 1	Sample Output 1
7 12 0	6 4

Hide

Please log in to submit a solution to this problem

Log in

CPU Time limit1 second

Memory limit1024 MB

?

DifficultyNot Available

LinksStatistics

DownloadsSample data files

Source & LicenseWaterloo Programming Contest 2002-06-01For educational use only

You haven't made any submissions on this problem yet.

Editor:

Problem ERelatives

Input

Output

Problem E
Relatives