该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 L 喜欢分块，于是小 L 给了你一个正整数 $n$，你需要统计有多少个不超过 $n$ 的正整数 $x$ 满足 $\lfloor \sqrt{x} \rfloor$ 是 $x$ 的因数。

因为小 L 怕你浑水摸鱼，所以小 L 给了你 $q$ 组不同的询问 $n_1, \ldots, n_q$，每组询问的 $n_i$ 可能不同。你需要对每个 $n = n_i$ 求出正确答案。

题面中的 $\lfloor \rfloor$ 为向下取整符号，$\lfloor a \rfloor$ 表示最大的不超过 $a$ 的整数。例如，$\lfloor 1.9\rfloor = 1$，$\lfloor 7 \rfloor = 7$，而 $\lfloor \pi \rfloor =3$。

输入格式

第一行，一个整数 $q$。

接下来 $q$ 行，第 $i$ 行一个正整数 $n_i$，表示第 $i$ 组询问对应的 $n$ 的值。

输出格式

输出共 $q$ 行。

第 $i$ 行输出一个整数，表示 $n = n_i$ 时小 L 的问题的答案。

5
1
3
6
10
15

1
3
5
7
9

提示

【样例解释 #1】

对 $n = 6$，共有 $5$ 个不超过 $6$ 的正整数 $x$ 符合题意：

• 若 $x = 1$，$\lfloor \sqrt{x} \rfloor = 1$，由于 $1$ 是 $1$ 的因数，所以 $x = 1$ 符合条件；
• 若 $x = 2$，$\lfloor \sqrt{x} \rfloor = 1$，由于 $1$ 是 $2$ 的因数，所以 $x = 2$ 符合条件；
• 若 $x = 3$，$\lfloor \sqrt{x} \rfloor = 1$，由于 $1$ 是 $3$ 的因数，所以 $x = 3$ 符合条件；
• 若 $x = 4$，$\lfloor \sqrt{x} \rfloor = 2$，由于 $2$ 是 $4$ 的因数，所以 $x = 4$ 符合条件；
• 若 $x = 5$，$\lfloor \sqrt{x} \rfloor = 2$，由于 $2$ 不是 $5$ 的因数，所以 $x = 5$ 不符合条件；
• 若 $x = 6$，$\lfloor \sqrt{x} \rfloor = 2$，由于 $2$ 是 $6$ 的因数，所以 $x = 6$ 符合条件。

类似地，可以得到 $n$ 取 $1, 3, 10, 15$ 时的答案分别为 $1, 3, 7$ 和 $9$。

其余样例下载

点我下载其余样例

【样例 #2】

见附件中的 $\texttt{\texttt{sqrt/sqrt2.in}}$ 与 $\texttt{\texttt{sqrt/sqrt2.ans}}$。

该组样例满足测试点 $1\sim 2$ 的约束条件。

【样例 #3】

见附件中的 $\texttt{\texttt{sqrt/sqrt3.in}}$ 与 $\texttt{\texttt{sqrt/sqrt3.ans}}$。

该组样例满足测试点 $4$ 的约束条件。

【样例 #4】

见附件中的 $\texttt{\texttt{sqrt/sqrt4.in}}$ 与 $\texttt{\texttt{sqrt/sqrt4.ans}}$。

该组样例满足测试点 $6$ 的约束条件。

【样例 #5】

见附件中的 $\texttt{\texttt{sqrt/sqrt5.in}}$ 与 $\texttt{\texttt{sqrt/sqrt5.ans}}$。

该组样例满足测试点 $7 \sim 8$ 的约束条件。

【样例 #6】

见附件中的 $\texttt{\texttt{sqrt/sqrt6.in}}$ 与 $\texttt{\texttt{sqrt/sqrt6.ans}}$。

该组样例满足测试点 $9 \sim 10$ 的约束条件。

【数据范围】

本题共 $10$ 个测试点，每个 $10$ 分。

对于所有数据，保证：

• $1 \leq q \leq 10^5$；
• $1 \leq n_i \leq 10^{18}$。

• 特殊性质：保证 $n_i$ 是完全平方数。