问题描述

这是一道模板题。

首先给出欧拉函数的定义：即 $\mathsf{\Phi}(n)$ 表示的是小于等于 $n$ 的数中和 $n$ 互质的数的个数。

比如说 $\mathsf{\Phi}(6)=2$，当 $n$ 是质数的时候，显然有 $\mathsf{\Phi}(n)=n-1$。

题目大意：

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

输入格式

输入共两行。

第一行输入一个整数表示 $n$ 。

第二行输入 $n$ 个整数。

输出格式

输出共 $n$ 行，每行输出 $1$ 个整数表示对应数字的欧拉函数。

样例输入

3
3 6 8

样例输入

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]$ 。