608 - 欧拉函数

通过次数

21

提交次数

32

时间限制 : 1 秒
内存限制 : 128 MB

欧拉函数是小于或等于n的正整数中与n互质的数的数目,即满足gcd(x,n)=1.

wlxsq现在有m次询问,你都能够回答上来吗?

输入

第一行是一个整数m,表示询问的次数。

接下来有m行正整数n,表示wlxsq当前查询数字n

输出

对于每一个n,输出其对应的个数。

样例

输入

2
25608
24027

输出

7680
16016

提示

数据规模

对于100\%的数据,有 2\le n,m \le 32768;