Euler's Totient Function

Problem Description

Read $T$, then $T$ test cases follow. Each case gives one number $n$; output its Euler's totient function $\varphi(n)$.

Input Format

The first line contains one integer $T$.

Each of the next $T$ lines contains one number $n$.

Output Format

Output $T$ lines, each containing one number: the value of $\varphi(n)$ for that $n$.

Sample Input

2
12345
987654321

Sample Output

6576
619703040

Constraints

For $100\%$ of the test cases, $1 \le T \le 10^3$ and $1 \le n \le 10^9$.