题目描述

Cristobal 有一个包含 $N$ 个（可能为负）整数的数组。数组中第 $i$ 个整数为 $A_i$。数组的一个连续非空子数组称为 完美的，如果它的总和是一个 完全平方数。完全平方数是某个非负整数与自身相乘得到的数。例如，前五个完全平方数是 $0$、$1$、$4$、$9$ 和 $16$。

请问有多少个子数组是完美的？如果两个子数组在数组中的起始或结束下标不同，则视为不同，即使它们包含相同的值且顺序相同。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含整数 $N$。第二行包含 $N$ 个整数，描述 Cristobal 的数组。其中第 $i$ 个整数为 $A_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是完美子数组的数量。

3
3
2 2 6
5
30 30 9 1 30
4
4 0 0 16

Case #1: 1
Case #2: 3
Case #3: 9

提示

在样例 #1 中，有一个完美子数组：$[2, 2]$，其和为 $2^2$。

在样例 #2 中，有三个完美子数组：

• $[9]$，其和为 $3^2$。
• $[1]$，其和为 $1^2$。
• $[30, 30, 9, 1, 30]$，其和为 $10^2$。

在样例 #3 中，有九个完美子数组：

• $[4]$，其和为 $2^2$。
• $[4, 0]$，其和为 $2^2$。
• $[4, 0, 0]$，其和为 $2^2$。
• $[0]$，其和为 $0^2$。
• $[0, 0]$，其和为 $0^2$。
• $[0, 0, 16]$，其和为 $4^2$。
• $[0]$，其和为 $0^2$。
• $[0, 16]$，其和为 $4^2$。
• $[16]$，其和为 $4^2$。

注意：对于本题的测试集 2，我们不建议使用解释型/较慢的语言。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$-100 \le A_i \le 100$。

测试集 1

$1 \le N \le 1000$。

测试集 2

最多 $5$ 个测试用例满足 $1 \le N \le 10^5$。

其余测试用例满足 $1 \le N \le 1000$。

翻译由 DeepSeek V4 Pro 完成