#1298. 完全平方数的个数

完全平方数的个数

题目描述

若一个整数 xx 可以表示为另一个整数的平方,那么 xx 称为“完全平方数”。

输入 nn,求 1n1 \sim n 中完全平方数的个数。

本题有多组输入。对于每一组输入,你都需要求出对应的答案。

输入格式

第一行:一个整数 TT,表示输入数据的组数

此后 TT 行:每行输入一个整数 nin_i

输出格式

对于每组输入数据,输出一个答案,表示 1n1 \sim n 中完全平方数的个数。每个答案独占一行。

样例

3
1
10
1000
1
3
31

样例 11 解释

对于第二组输入:1101 \sim 10 之间的完全平方数有 1,4,91,4,9 三个。

数据规模与约束

对于 40%40\% 的数据,T=11n104T=1,1≤n≤10^4

对于 80%80\% 的数据,T=11n1012T=1,1≤n≤10^{12}

对于 100%100\% 的数据,1T1061n10121≤T≤10^6,1≤n≤10^{12}