给出一个正整数n，计算小于n且与n互素的正整数有多少个？两个整数a和b是互素的，当且仅当不存在正整数x＞1，y＞0和z＞0，使得a＝xy和b＝xz。

有多个测试例。每个测试例一行，输入n（n≤1 000 000 000），当为0时输入结束。

对每个测试输出一行，输出相应的结果。

ZOJ