Description

欧拉函数 $\varphi(n)$ 表示 $[1, n]$ 中与 $n$ 互质的正整数的个数。

给定若干个 $n$，分别求 $\varphi(n)$。

Input Format

共 $T$ 行，每行一个数 $n$。

Output Format

共 $T$ 行，每行一个数 $\varphi(n)$。

Sample

样例输入

33
8657
3124
4324
45345

样例输出

20
7860
1400
2024
24176

Hint

$1 \leq T, n \leq 3 \times 10 ^ 6$