{"raw_statement":[{"iden":"background","content":"钟离很喜欢数学题。"},{"iden":"statement","content":"其中一个问题是这样的：定义一个丘丘人是可以被击杀的，当且仅当存在一个大于 $1$ 的完全平方数能够整除它的编号。比如，$12$ 号丘丘人就是可以被击杀的，因为它能够被 $4$ 整除；$15$ 号丘丘人则不能被击杀。请计算编号为 $1\\sim n$ 中的丘丘人中能够被击杀的个数。由于钟离秉承着“差不多得了”的做事理念，因此，他允许你的答案与真正的答案有着不超过 $2\\times10^4$ 的绝对误差。"},{"iden":"input","content":"**本题多组询问**。第一行输入一个数 $T$，表示询问组数。\n\n每组询问输入一行，一个正整数 $n$。"},{"iden":"output","content":"对于每组询问，输出一行一个整数，表示编号为 $1\\sim n$ 中的丘丘人中能够被击杀的个数。"},{"iden":"note","content":"#### 样例解释\n\n$1\\sim 10$ 中，只有 $4,8,9$ 这 $3$ 个丘丘人可以被击杀，因此答案为 $3$。\n\n需要注意的是，由于你的答案被允许与标准答案有 $2\\times 10^4$ 的绝对误差，因此 $-2,3,20003$ 等输出都将被认为是正确的。\n\n#### 数据范围\n\n- $\\text{Subtask 1(10 pts)}$：$n\\le 10^5$。\n- $\\text{Subtask 2(20 pts)}$：$n\\le 10^7$。\n- $\\text{Subtask 3(20 pts)}$：$n\\le 10^9$。\n- $\\text{Subtask 4(20 pts)}$：$T=1$。\n- $\\text{Subtask 5(30 pts)}$：无特殊性质。\n\n对于 $100\\%$ 数据，满足 $1\\le n\\le 10^{18}$，$1\\le T\\le 10^4$，保证 $n$ 在范围内随机得到。"}],"translated_statement":null,"sample_group":[["3\n10\n32678\n9686985\n","3\n12814\n3797988"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}