该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

Tom猫这天抓到了Jerry鼠并把Jerry关在一个透明玻璃盒子里面，Jerry被关了一天，很饿了，求Tom放它出来吃东西。
Tom表示如果Jerry能帮它解答一道数学题，就放它出来，并且送牛奶给Jerry喝，这道数学题是这样的： 有一个正整数n，求1--n内，有多少个数与n互质。 
Jerry的数学很差，饿急了的它向你求助，请你帮它计算下。 

输入格式

输入一行包含一个整数n。

输出格式

输出一行一个整数，即有多少个数与n互质。

样例

10000

4000

提示

数据范围： 20%数据：$1<=n<=10^3$ 90%数据：$1<=n<=5*10^6$ 100%数据：$1<=n<=2*10^7$