题目描述

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

欧拉函数的定义：

$1$ ~ $N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。 若在算数基本定理中，$N = p_1^{a_1}p_2^{a_2}...p_m^{a_m}$，则： $\varphi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times...\times\frac{p_m-1}{p_m}$

输入格式

第一行包含整数 $n$（$1\leq n \leq 100$）。

接下来 $n$ 行，每行包含一个正整数 $a_i$（$1\leq a_i \leq 2\times10^9$）。

输出格式

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

输入样例

3
3
6
8

输出样例

2
2
4

提示

对于第一个样例

与 $3$ 互质的数有：$1,2$，共 $2$ 个。

对于第三个样例

与 $8$ 互质的数有：$1,3,5,7$，共 $4$ 个。