• Cho một số nguyên ~N~, hãy đếm có bao nhiêu số nguyên dương ~i \le N~ sao cho ~\text{gcd(i, N) = 1}~.
• Lưu ý: ~\text{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~.

Input

• Dòng đầu tiên chứa ~1~ số nguyên ~T (1 \le T \le 10)~ là số lượng test,
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N (1 \le N \le 10^9)~.

Output

• 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.

Sample

Input #1

5
100
200
155
210
985

Output #1

40
80
120
48
784