Background

Zhongli really likes math problems.

Problem Description

One of the problems is as follows: Define a Hilichurl as killable if and only if there exists a perfect square greater than $1$ that can divide its index. For example, Hilichurl $12$ is killable because it is divisible by $4$; Hilichurl $15$ is not killable. Please calculate how many Hilichurls with indices $1\sim n$ are killable. Since Zhongli follows the principle of “that’s about enough,” he allows your answer to have an absolute error of at most $2\times10^4$ compared to the true answer.

Input Format

This problem contains multiple queries. The first line contains an integer $T$, representing the number of queries.

Each query contains one line with a positive integer $n$.

Output Format

For each query, output one line containing an integer, representing the number of killable Hilichurls with indices $1\sim n$.

3
10
32678
9686985

3
12814
3797988

Hint

Sample Explanation

Among $1\sim 10$, only the $3$ Hilichurls $4,8,9$ are killable, so the answer is $3$.

Note that since your output is allowed to have an absolute error of $2\times 10^4$ from the standard answer, outputs such as $-2,3,20003$ will all be considered correct.

Constraints

• $\text{Subtask 1(10 pts)}$: $n\le 10^5$.
• $\text{Subtask 2(20 pts)}$: $n\le 10^7$.
• $\text{Subtask 3(20 pts)}$: $n\le 10^9$.
• $\text{Subtask 4(20 pts)}$: $T=1$.
• $\text{Subtask 5(30 pts)}$: no special properties.

For $100\%$ of the testdata, it holds that $1\le n\le 10^{18}$, $1\le T\le 10^4$, and $n$ is guaranteed to be chosen randomly within the range.

Translated by ChatGPT 5