题目描述

一个考古学家正在考察一座古代城市，发现一个有部分毁坏的石墙，有几行奇异的数。这些数的前几位完整无缺，但其他数字由于侵蚀作用而无法辨认。他猜想这个石墙上原先的所有数都是一个完全平方数。他选择了能看清楚的一些数写成列表交给你，请你求出最小的数，使得它的平方与他提供的列表中的数一致。编程，对于给定的整数 \(N\)，求出最小的完全平方数(如果存在)，使这个数的前若干位与 \(N\) 相同。

格式

输入格式

第一行为正整数 \(t(≤50)\)，表示数据组数；接下来每行一个正整数 \(n（＜10^8)\)。

输出格式

对于每个 \(n\)，输出最小的正整数 \(E\)，使得 \(n\) 恰好是它的平方数的前几位。

样例1

输入样例1

2
3
36

输出样例1

6
19

样例解释

样例 \(1\)，\(6\) 的平方是 \(36\)；样例 \(2\)，\(19\) 的平方是 \(361\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T2\)

文件IO

freopen("dilemma.in","r",stdin);
freopen("dilemma.out","w",stdout);