给定 n 个正整数 ai ，请你求出每个数的欧拉函数。
欧拉函数的定义
中与 互质的数的个数被称为欧拉函数，记为 。 若在算数基本定理中，，则： =
第一行包含整数 n 。
接下来 n 行，每行包含一个正整数 ai
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
样例输入
3 3 6 8
样例输出
2 2 4