暂无测试数据。

这里我们定义 $\varphi(n)$ 表示所有小于等于 $n$ 与 $n$ 互质数的个数。

例如 $\varphi(10) = 4$，因为我们可以在 $1 \sim 10$ 中找到 $1,3,7,9$ 与 $10$ 互质。

输入格式

第一行输入一个整数 $t$，表示测试数据组数。

接下来 $t$ 行，每行有一个整数 $n$。

输出格式

对于每组测试数据输出 $\varphi(n)$ 。

数据范围

$1 \le t \le 100, 1 \le n \le 10^{10}$。

3
2
10
100

1
4
40