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
sssdhnam: 2023-09-16 15:13:14

hope I could AC it in 10 times ☺

berlin03spoj: 2023-07-11 12:50:04

hic AC in 5 times :((

shakur01: 2022-09-09 13:05:38

AC in the first go.

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