题目描述

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

输入

第一行包含整数 $n$。

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

输出

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

3
3
6
8

2
2
4

提示

$1≤n≤100$,

$1≤a_i≤2×10^9$