Phản bình phương


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.