U271924 欧拉函数基础2

给定一个整数 $n(2 \le n \le 10^8)$，求 $n$ 以内与 $n$ 互质的数的个数。 注：本题中互质的含义是最大公约数为 $1$。

输入包含多组测试数据，输入的第一行包含一个整数 $t(1 \le t \le 2 \times 10^6)$，表示测试数据组数。 接下来每一行包含一个整数 $n(1 \le n \le 10^7)$，表示一组测试数据。

对于每组测试数据，输出一行，包含一个整数，表示 $n$ 以内与 $n$ 互质的数的个数。