题目描述

给定 $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}$

输入格式

第一行包含整数 $n$。

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

输出格式

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

数据范围

$1≤n≤100$，

$1≤a_i≤2$ x $10^9$

输入样例：

3
3
6
8

输出样例：

2
2
4