Ta định nghĩa hàm ~phi(n)~ là số lượng số nguyên dương bé hơn hoặc bằng ~n~ và nguyên tố cùng nhau với ~n~. Ta coi ~phi(1) = 1~.

Cho ~q~ truy vấn, mỗi truy vấn gồm một số nguyên dương ~n~, hãy in ra ~phi(n)~.

Input

• Dòng đầu gồm số nguyên dương ~q \le 100000~.
• ~Q~ dòng sau, mỗi dòng gồm một số ~n \le 1000000~ miêu tả ~q~ truy vấn.

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

5
15
17
14
18
17

Output:

8
16
6
6
16