题目背景

班级里有 $n$ 枚徽章，每枚徽章有一个正整数积分。老师允许进行若干次调整：从一枚积分至少为 $2$ 的徽章上取走 $1$ 分，转移到另一枚不同的徽章上。

老师认为一个积分是优秀值，当且仅当这个数本身是完全平方数，并且它的数位之和也是完全平方数。

题目描述

对于每组数据，给定所有徽章的初始积分。你可以进行任意次调整，求最多能让多少枚徽章的积分变成优秀值。

完全平方数指可以写成某个整数平方的数，例如 $0,1,4,9,16,25,36,49,64,81$。

输入格式

每个测试文件包含多组测试数据。第一行输入整数 $T$，表示数据组数，$1 \le T \le 10^4$。

每组数据第一行输入一个正整数 $n$，表示徽章数量，$1 \le n \le 100$。

第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每枚徽章的积分，$1 \le a_i \le 200$。

同一个测试文件中的 $n$ 总和没有限制。

输出格式

对于每组数据，输出一行一个整数，表示答案。

样例

2
4
8 10 3 5
1
2

4
0

提示

样例解释

第一组数据中，可以先把 $10$ 调整为 $9$，把 $8$ 调整为 $9$；再把 $5$ 调整为 $4$，把 $3$ 调整为 $4$，最后四枚徽章的积分都为优秀值。

第二组数据只有一枚积分为 $2$ 的徽章，无法通过调整让它变成优秀值。

数据范围

• 前 $30\%$ 的数据，$1 \le n \le 3$。
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 100$，$1 \le a_i \le 200$。

本题需要文件读写

输入文件名为 PS.in。

输出文件名为 PS.out。

文件读写说明

使用 freopen("PS.in", "r", stdin); 将标准输入重定向到输入文件，使用 freopen("PS.out", "w", stdout); 将标准输出重定向到输出文件。

在 main() 函数下面的第一行添加：

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