Background

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

Input

第一行包含整数$n$。

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

Output

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

Samples

3
3
6
8

2
2
4

Limitation

$1≤n≤100,$

$1≤a_i≤2×10^9$