Cho một số nguyên ~N~, hãy đếm có bao nhiêu số nguyên dương ~i~ không vượt quá ~N~ sao cho ~GCD(i, N) = 1~.

Lưu ý: ~GCD(a, b) = c~ với ~c~ là số nguyên dương lớn nhất mà ~a~ và ~b~ đều chia hết cho ~c~.

Dữ liệu

• Dòng đầu tiên chứa 1 số nguyên ~T~ là số lượng test ~(1 \le T \le 10)~.

• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~ ~(1 \le N \le 10^9)~.

Kết quả

Gồm ~T~ dòng, mỗi dòng chứa kết quả bài toán ứng với mỗi test case.

Ví dụ

Sample Input

5
100
200
155
210
985

Sample Output

40
80
120
48
784

Chấm điểm

• Subtask ~1~ (~50\%~ số điểm): ~1 \le N \le 10^5~.

• Subtask ~2~ (~50\%~ số điểm): không có giới hạn gì thêm.