Description

小叶子挖啊挖啊挖宝藏，挖到了许多宝箱，小叶子可高兴啦！
可是宝箱上面都上着密码锁...这不是在逗小叶子吗？
每个箱子上都标有一个编号x，可是密码是多少呢？
小叶子只能继续挖啊挖啊，发现了好几个开着的箱子，这些箱子的密码都保留着╰(￣▽￣)╮
小叶子整理了一下，发现这些箱子的编号和密码分别是（2,1）（3,2）（4,2）（9,6）（10,4）（11,10）...（编号，密码）。小叶子苦苦研究了100天，发现密码就是编号的欧拉函数！！！
（对正整数x，欧拉函数是少于或等于x的数中与x互质的数的数目）,现在小叶子想知道所有箱子的密码，你能告诉他吗？

Input

多组测试数据
每组有一个数x(1 < x < 1000)

Output

输出这个箱子的密码

Sample Input

5
6
7
8

Sample Output

4
2
6
4

HINT

Source

NBU KissM