题目描述

小明在操场上铺正方形的地垫，地垫的块数只能是完全平方数（$1, 4, 9, 16, 25, \dots$），这样才能拼成一个大正方形。

老师给出了 $n$ 个数，对于每个数 $x$，请你找出与 $x$ 最接近的完全平方数，也就是使 $|k^2 - x|$ 最小的那个 $k^2$（$k$ 是正整数）。

可以证明，不会出现两个完全平方数与 $x$ 一样接近的情况。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个正整数 $x_1, x_2, \dots, x_n$。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示与 $x_i$ 最接近的完全平方数。

样例 #1

样例输入 #1

5
10 1 13 50 99

样例输出 #1

9
1
16
49
100

样例解释

• $10$ 与 $9$ 相差 $1$，与 $16$ 相差 $6$，所以答案是 $9$；
• $1$ 本身就是完全平方数；
• $13$ 与 $9$ 相差 $4$，与 $16$ 相差 $3$，所以答案是 $16$；
• $50$ 最接近 $49$，$99$ 最接近 $100$。

提示

数据范围

• 对于 $30\%$ 的数据：$x_i \le 10^4$；
• 对于 $60\%$ 的数据：$x_i \le 10^9$；
• 对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le x_i \le 10^{18}$。

提示

• $x_i$ 最大到 $10^{18}$，要用 long long 存储；一个一个地试 $k$ 太慢了。
• 可以用 sqrt 先算出 $\sqrt{x}$ 的大概值，但 sqrt 的结果是浮点数，数很大时可能有一点误差。转成整数 $r$ 以后，最好再用 while 检查一下：保证 $r^2 \le x < (r+1)^2$。
• 答案一定是 $r^2$ 和 $(r+1)^2$ 中的一个。