Problem 1090 --互质

1090: 互质

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 302  Solved: 85
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

给你一个正整数n,请问有多少个比n小的且与n互质的正整数?
两个整数互质的意思是,这两个整数没有比1大的公约数。

Input

输入包含多组测试数据。每组输入是一个正整数n(n<=1000000000)。当n=0时,输入结束。

Output

对于每组输入,输出比n小的且与n互质的正整数个数。

Sample Input

7
12
0

Sample Output

6
4

HINT

Source

[Submit][Status]