Đếm Số Không Chứa Bình Phương

Với mỗi truy vấn $N$, hãy đếm các số nguyên dương không vượt quá $N$ mà không chia hết cho bình phương của bất kỳ số nguyên tố nào.

Một số như vậy được gọi là không chứa bình phương. Số $1$ cũng được tính là không chứa bình phương.

Input

• Dòng đầu chứa số truy vấn $T$.
• Mỗi trong $T$ dòng tiếp theo chứa một số nguyên dương $N$.

Output

• Với mỗi truy vấn, in một dòng là số lượng số không chứa bình phương trong đoạn từ $1$ đến $N$.

Constraints

• $1\le T\le 100.$
• $1\le N\le 10^{14}.$

Scoring

• Subtask $1$ ($50\%$ số điểm): $T\le 10$ và $N\le 10^7$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
1
10
30
100

1
7
19
61