Số thanh nhã

Với một số nguyên dương $x$, phân tích ra thừa số nguyên tố của nó có dạng

$$x=2^{k_1}·3^{k_2}·5^{k_3}·\dots$$

Gọi $x$ là số thanh nhã nếu ước chung lớn nhất của dãy các số mũ $k_1,k_2,\dots$ (chỉ tính các số mũ khác $0$) bằng $1$.

Ví dụ: $5=5^1$, $12=2^2·3^1$, $72=2^3·3^2$ là các số thanh nhã; còn $8=2^3$ (ƯCLN $=3$) và $2500=2^2·5^4$ (ƯCLN $=2$) thì không.

Cho số nguyên $n$, hãy đếm số lượng số thanh nhã trong đoạn từ $2$ đến $n$.

Có nhiều truy vấn, mỗi truy vấn cho một giá trị $n$ và cần được xử lý độc lập.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $T$ — số lượng truy vấn.
• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên $n_i$.

Dữ liệu ra

In ra $T$ dòng, dòng thứ $i$ là số lượng số thanh nhã trong đoạn $[2,n_i]$.

Ràng buộc

• $1\le T\le {10}^5$
• $2\le n_i\le {10}^{18}$

Ví dụ