ETF - Euler Totient Function


Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/etf


Trong số học, hàm Ơ-le của một số nguyên dương n được định nghĩa là số lượng các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n.

Cho số nguyên dương n (1 <= n <= 10^6). Tính giá trị của hàm Ơ-le .

Input

Dòng đầu chứa số nguyên T là số test (T <= 20000)

T dòng tiếp theo, mỗi dòng chứa một số nguyên n.

Output

T dòng, mỗi dòng ghi kết quả của test tương ứng.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
2
4


hide comments
ishraaq_56789: 2021-05-20 10:58:36

Proud to write an Euler Totient function from scratch and get an AC in the first go.


Added by:Race with time
Date:2009-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET