问题 H: 欧拉函数

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

欧拉函数的定义

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N=p₁^a1p₂^a2…p_N^am，则：
ϕ(N) = N × (p₁ − 1) / p₁ × (p₂ − 1) / p₂ × … × (p_m - 1) / p_m

第一行包含整数 n。

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

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

3
3
6
8

2
2
4