Cho một số nguyên dương \(n\), hãy ¬đếm xem 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\).

Input

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

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

Output

• Gồm T dòng: mỗi dòng chứa kết quả của bài toán tương ứng với mỗi test.

Ràng buộc:

• Subtask 1: Có 50% số test ứng với 50% số điểm thoả mãn: \(n≤ 10^5;\)

• Subtask 2: Có 50% số test còn lại ứng với 50% số điểm thoả mãn: \(n≤10^9.\)

Sample Input

5
100
200
155
210
985

Sample Output

40
80
120
48
784