python 代码

t=int(input())
for t in range(t):
    a=int(input())
    i=2
    res=a
    while i<=a//i: #质数成对，所以只用循环到a**0.5
        if a%i==0:
            res=res/i*(i-1) #欧拉函数
            while a%i==0:
                a/=i #一直整除，整除了多少次就是当前i的指数
        i+=1
    if a>1:#说明还有一个最大的质数
        res=res/a*(a-1)
    print(int(res))