题目描述

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

输入格式

第一行一个数字 $T$。

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

输出格式

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

2
12345
987654321

6576
619703040

数据范围

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