Description

给定 n个正整数 $a_i$，请你求出每个数的欧拉函数。
欧拉函数的定义
1∼N中与N互质的数的个数被称为欧拉函数，记为$ ϕ(N)$。
若在算数基本定理中，$N=p_1^{a_1}p_2^{a_2}…p_m^{a_m},$则：
$ϕ(N)=N×\frac{P_1-1}{P_1} ×\frac{P_2-1}{P_2} ×…×\frac{P_m-1}{P_m}$

Input Format

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

Output Format

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

3
3
6
8

2
2
4

Hint

1≤n≤100,
$1≤a_i≤2×10^9$

Source

2.4数学知识 欧拉函数