编程题
### 问题描述
这是一道模板题。
首先给出欧拉函数的定义：即 $\mathsf{\Phi}(n)$ 表示的是小于等于 $n$ 的数中和 $n$ 互质的数的个数。
比如说 $\mathsf{\Phi}(6)=2$，当 $n$ 是质数的时候，显然有 $\mathsf{\Phi}(n)=n-1$。
**题目大意**：
给定 $n$ 个正整数，请你求出每个数的欧拉函数。
### 输入格式
输入共两行。
第一行输入一个整数表示 $n$ 。
第二行输入 $n$ 个整数。
### 输出格式
输出共 $n$ 行，每行输出 $1$ 个整数表示对应数字的欧拉函数。
### 样例输入
```text
3
3 6 8
```
### 样例输入
```text
2
2
4
```
### 说明
小于等于 $3$ 的数中与 $3$ 互质的有：$1,2$。
小于等于 $6$ 的数中与 $6$ 互质的有：$1,5$。
小于等于 $8$ 的数中与 $8$ 互质的有：$1,3,5,7$。
### 评测数据规模
保证对于所有数据有：
$1 \leq n \leq 100$，输入的 $n$ 个整数范围为 $[1,2\times10^9]$ 。