Phản bình phương
Một số được gọi là phản bình phương (square free) nếu nó không chia hết cho bất kì số chính phương nào khác 1.
Hãy đếm số lượng số nguyên dương không vượt quá $N$ là phản bình phương.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $T \ (0<T\le5)$ - số lượng bộ test.
- $T$ dòng tiếp theo, mỗi dòng chứa số nguyên $N \ (0<N\le10^{12})$.
Kết quả
- In trên $T$ dòng, mỗi dòng là kết quả cho mỗi truy vấn sau khi chia lấy dư cho $10^9+7$.
Ví dụ
Ví dụ 1
input
3
10
100
1000
output
7
61
608
Comments