Rất may mắn trong đại dịch, độ an toàn của khu bạn sống là rất tốt và được gọi là vùng xanh. Tuy nhiên vẫn còn một số vùng chưa xác định được. Chính phủ biết bạn là một lập trình viên giỏi và nhờ bạn xác định xem còn bao vùng bị gọi là nguy hiểm ở một số thành phố.

Ở trong thành phố \(𝑁\) có \(𝑁 − 1\) vùng với chỉ số lần lượt là \(2, 3, … , 𝑁\). Gọi chỉ số của một vùng là \(𝑥\). Biết khi phân tích thành các thừa số nguyên tố, ta sẽ có \(x = p1^{k_1} * p2^{k_2} * … * pz^{k_z}\). Số \(𝑥\) được gọi là số bất khả căn nếu \(GCD(k_1, k_2 ,… , k_n ) = 1\). Và các vùng có chỉ số là số bất khả căn sẽ bị coi là nguy hiểm và lập tức cần tăng cường hỗ trợ.

Yêu cầu: Cho \(M\) truy vấn, với mỗi truy vấn, cho số nguyên \(N\). Tính số lượng vùng nguy hiểm trong thành phố \(N\).

Input

• Dòng 1 chứa số nguyên \(M (M ≤ 10^4)\).

• \(M\) dòng tiếp theo, mỗi dòng chứa số nguyên \(N( N ≤ 10^{18})\)

Output

• In ra trên \(M\) dòng, mỗi dòng ghi một số là số lượng vùng nguy hiểm trong thành phố \(N\) tương ứng.

Giới hạn:

• Subtask 1: \(M = 1, N ≤ 10000\)

• Subtask 2: \(M = 10^4, N ≤ 10^6\)

• Subtask 3: Không có thêm ràng buộc nào cả.

Sample Input

1
100000

Sample Output

99633