题目描述

多组询问，每组询问给定一个数字 $n$，你需要求出 $\varphi(n)$

输入格式

第一行输入一个整数 $t,1\leq t\leq 10^{5}$

接下来 $t$ 行每行一个整数 $n$，$1\leq n\leq 10^7$

输出格式

输出一个整数代表答案

3
2
3
5

1
2
4