U203244 欧拉函数

欧拉函数的定义 1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。 若在算数基本定理中，N=p1^a1p2^a2…pm^am，则： ϕ(N) = N×(p1−1)/p1×(p2−1)/p2×…×(pm−1)/pm

给定 n 个正整数 ai，请你求出每个数的欧拉函数。

第一行包含整数 n。 接下来 n 行，每行包含一个正整数 ai

输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围 1≤n≤100, 1≤ai≤2×10^9