题目背景

欧拉函数是小于m的正整数中与m互质的数的数目，记为φ(m)。

φ(m)的通项公式为:

其中p为m的质因子。

例如求φ(700)，先分解质因数，700=2×2×5×5×7，p1=2，p2=5，p3=7，

φ(700)=700×(1-1/2)×(1-1/5)×(1-1/7)=240。

题目描述

输入m，计算φ(m)。

输入格式

一个整数m(m<10^6)。

输出格式

一个整数φ(m)。

输入/输出样例

700

240

说明/提示

时间1000ms，内存256MiB