题目描述

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

输入 $n$，求 $1 \sim n$ 中完全平方数的个数。

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

输入格式

第一行：一个整数 $T$，表示输入数据的组数

此后 $T$ 行：每行输入一个整数 $n_i$

输出格式

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

样例

3
1
10
1000

1
3
31

样例 $1$ 解释

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

数据规模与约束

对于 $40\%$ 的数据，$T=1，1≤n≤10^4$。

对于 $80\%$ 的数据，$T=1，1≤n≤10^{12}$。

对于 $100\%$ 的数据，$1≤T≤10^6，1≤n≤10^{12}$。