解题思路
只需考虑完全平方数。设 x=i2≤n，将其转为字符串 s，枚举所有切分点，将其分为左右两段：
- 两段都非空；
- 不允许有前导零（除单独的
"0"）；
- 转为整数后，两段都必须是完全平方数。
为快速判断某个数是否为完全平方数，预处理所有不超过 109 的平方数，存入哈希集合。
P4678.第2题-完全平方数
题目内容
定义一个正整数为完完全全平方数，当且仅当同时满足：
- 该数本身是完全平方数；
- 存在一个切分点，使得在该切分点将该数的十进制表示切分为两段后，两段均非空且对应的十进制整数也都是完全平方数。
- 切分处只能发生在相邻两位之间；任一段不允许有前导零（除非该段仅为单个字符 "0"）。
例如：若我们使用 ∣标记切分点，在整数 16 中，唯一的切分点为 16∣1，因为 16 和 1 均是完全平方数（但 161 不是 “完完全全平方数”，因为它本身不是完全平方数）；在整数 1601 中，不存在满足条件的切分点。
给定上界 n，问不超过 n 的完完全全平方数共有多少个。
名词解释
完全平方数：一个数如果可以表示为某个整数的平方，那么这个数就是完全平方数。例如，前十个完全平方数是 0,1,4,9,16,25,36,49,64,81。
输入描述
每个测试文件均包含多组测试数据：
- 第一行输入一个整数 T(1≤T≤50)，表示数据组数；
- 此后 T 行，每行输入一个整数 n(1≤n≤109)，表示上界。
输出描述
对于每一组测试数据，新起一行，输出一个整数，表示满足条件的数的个数。
样例1
输入
1
50
输出
1 3 5 5 5
说明
- 不超过50的正完全平方数为{1,4,9,16,25,36,49}
- 只有49能被切成“4”和“9”，且二者均为完全平方数;
- 因此答案为1。
样例2
输入
1
1500
输出
5
