[[原文:http://acm.pku.edu.cn/JudgeOnline/problem?id=2407]]
----
''時間制限'':1000ミリ秒
''メモリ制限'':65536KB
&br;

*問題 [#y9ec9881]
正の整数nが与えられたとき、nより小さい正の整数で、nと互いに素なものの数を求めるプログラムを作成せよ。2つの正の整数a,bが互いに素であるというのは、x > 1, y > 0, z > 0であって、 a = xy, b = xzを満たす正の整数x,y,zが存在しないことをいう。 

*入力 [#xec77956]
入力はいくつかのテストケースを含む。各テストケースは1行で、各行は正の整数n(n <= 1,000,000,000)を含む。0のみを含む行は、テストケースの終わりである。 

*出力 [#qa6a5c2c]
各テストケースに対して、nより小さい正の整数で、nと互いに素なものの数を含む1行を出力せよ。 

*入力の例 [#d959ea95]
 7
 12
 0 

*出力の例 [#tb58a346]
 6
 4

*出典 [#r279aa56]
Waterloo local 2002.07.01