小苯的有趣数

题号：NC296703
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯发现了一些「有趣的」数字，即：数字本身是个完全平方数，且其各个数位之和也是个完全平方数！例如 $2025$ 本身就是个完全平方数，同时其各个数位之和： $2+0+2+5=9$ 也是个完全平方数，因此小苯认为 $2025$ 就是个「有趣的」数字。

$\hspace{15pt}$ 现在小苯有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ，他可以对 $a$ 做任意次以下操作：
$\hspace{23pt}\bullet\,$ 选择两个不同的下标 $i,j\left(1 \leqq i, j \leqq n;\,i \neq j\right)$ ，满足 $a_i \geqq 2$ ，随后将 $a_i$ 减去 $1$ ， $a_j$ 加上 $1$ 。
$\hspace{15pt}$ 他想知道，自己至多可以把 $a$ 中多少个数字变成「有趣的」数字，请你帮他算一算吧。

【名词解释】
$\hspace{15pt}$ 完全平方数：一个数如果可以表示为某个整数的平方，那么这个数就是完全平方数。前十个完全平方数是 $0,1,4,9,16,25,36,49,64,81$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行一个正整数 ，表示序列的长度。
第二行  个正整数 ，表示序列中的元素。
保证同一文件下的所有测试数据中，。
请注意，同一个测试文件中的  总和并没有限制大小。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示小苯至多可以把多少个数字变为「有趣的」。

示例1

输入

复制

输出

复制

4
0

说明

对于第一组测试数据：
选择  操作一次后，；
选择  操作一次后，。
此时所有数字都是「有趣的」。

对于第二组测试数据，显然无法进行操作，且  并不「有趣的」，因此答案为 。