#155. 「数论」欧拉函数(二)

内存限制:256 MiB 时间限制:1200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Menci

题目描述

欧拉函数 \varphi(n) 表示 [1, n] 中与 n 互质的正整数的个数。

给定若干个 n ,分别求 \varphi(n)

输入格式

T 行,每行一个数 n

输出格式

T 行,每行一个数 \varphi(n)

样例

样例输入

33
8657
3124
4324
45345

样例输出

20
7860
1400
2024
24176

数据范围与提示

1 \leq T, n \leq 3 \times 10 ^ 6