欧拉函数

题目描述

输入$T$，一共$T$组数据，每组一个数$n$，输出它的欧拉函数$\varphi(n)$。

输入格式

第一行一个数字$T$。

接下来$T$行，每行一个数字$n$。

输出格式

一共$T$行，每行一个数，表示这个数的欧拉函数$\varphi(n)$。

样例输入

2
12345
987654321

样例输出

6576
619703040

数据范围

对于$100\%$的数据，保证$1\leq T\leq 10^3, 1\leq n \leq 10^9$。