小苯发现了一些「有趣的」数字，即：数字本身是个
完全平方数，且其各个数位之和也是个
完全平方数！例如
本身就是个完全平方数，同时其各个数位之和：
也是个完全平方数，因此小苯认为
就是个「有趣的」数字。
现在小苯有一个长度为
的序列
，他可以对
做任意次以下操作：
选择两个不同的下标
)
，满足
，随后将
减去
，
加上
。
他想知道，自己至多可以把
中多少个数字变成「有趣的」数字，请你帮他算一算吧。
【名词解释】
完全平方数：一个数如果可以表示为某个整数的平方，那么这个数就是完全平方数。前十个完全平方数是
。
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数 )
代表数据组数，每组测试数据描述如下：
第一行一个正整数 )
，表示序列的长度。
第二行 
个正整数 )
，表示序列中的元素。
请注意，同一个测试文件中的 总和并没有限制大小。
输出描述:
对于每一组测试数据，新起一行输出一个整数，表示小苯至多可以把多少个数字变为「有趣的」。