#1到n中与n互质的个数
#欧拉公式 = n(1-1/p1)(1-1/p2)...(1-1/pk)
#容质原理
#1 从1~n中去掉p1,p2,...pk的所有倍数
#2 加上pi*pj的倍数
#3 减去pi*pj*pk的倍数
#...
#等于欧拉函数展开


if __name__ == '__main__':

    n = int(input())

    for i in range(n):
        x = int(input())
        res = x

        #分解质因数
        i = 2
        while i <= x//i:
            if x % i == 0:
                res = res // i * (i - 1)
                while  x % i == 0: x //= i
            i+=1

        if  x > 1 : res = res // x * (x - 1) 

        print(res)