题目描述

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

输入格式

第一行一个数字 $T$。

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

输出格式

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

3
12345
54321
97

6576
34272
96

数据范围

对于 100% 的数据，保证 $1≤T≤10^5,1≤n≤10^7$。