Euler's Totient Function

Problem Description

You are given $T$, representing $T$ groups of data. Each group contains one number $n$; output its Euler's totient function $\varphi(n)$.

Input Format

The first line contains a number $T$.

The next $T$ lines each contain a number $n$.

Output Format

A total of $T$ lines, each with one number representing the Euler's totient function $\varphi(n)$ of that number.

Sample Input

2
12345
987654321

Sample Output

6576
619703040

Constraints

For $100\%$ of the data, $1\leq T\leq 10^3, 1\leq n \leq 10^9$.