小周的有趣数

题目描述

小周同学发现了一些「有趣的」数字，即:数字本身是个完全平方数，且其各个数位之和也是个完全平方数! 例如 2025 本身就是个完全平方数，同时其各个数位之和:2+0+2+5=9也是个完全平方数，因此小周认为 2025 就是个「有趣的」数字。

现在小周有一个长度为 n 的序列 $a_1$,$a_2$,...,$a_n$，他可以对 a 做任意次以下操作: 选择两个不同的下标 i,j(1 ≤ i,j≤ n; i≠ j)，满足 $α_i$≥ 2，随后将 $a_i$ 减去 1，$a_j$ 加上 1 他想知道，自己至多可以把 a 中多少个数字变成「有趣的」数字，请你帮他算一算吧。

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

输入格式

注意，每个测试文件均包含多组测试数据。

第一行一个整数 T (1 ≤ T ≤ 10⁴)，表示测试数据组数 对于每组测试数据：

• 第一行一个整数 n (1 ≤ n ≤ 100)，表示序列长度
• 第二行 n 个正整数 a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 200)，表示序列元素

注意：请注意，同一个测试文件中的n总和并没有限制大小。

输出格式

对于每组测试数据，输出一个整数，表示最多可以变成"有趣的"数字的数量。

输入样例

2
4
8 10 3 5
1
2

输出样例

4
0

示例说明

第一组测试数据

输入序列: {8, 10, 3, 5}

操作步骤:

1. 选择 i=2, j=1 操作一次后，序列变为 {9, 9, 3, 5}
2. 选择 i=4, j=3 操作一次后，序列变为 {9, 9, 4, 4}

最终结果: 所有数字都变为「有趣的」数字

第二组测试数据

输入序列: {2}

操作情况:

• 无法进行任何操作
• 数字 2 本身不是「有趣的」数字

最终结果: 0