CF1352E.Special Elements

Pay attention to the non-standard memory limit in this problem.

In order to cut off efficient solutions from inefficient ones in this problem, the time limit is rather strict. Prefer to use compiled statically typed languages (e.g. C++). If you use Python, then submit solutions on PyPy. Try to write an efficient solution.

The array $a=[a_1, a_2, \ldots, a_n]$ ($1 \le a_i \le n$) is given. Its element $a_i$ is called special if there exists a pair of indices $l$ and $r$ ($1 \le l \lt r \le n$) such that $a_i = a_l + a_{l+1} + \ldots + a_r$. In other words, an element is called special if it can be represented as the sum of two or more consecutive elements of an array (no matter if they are special or not).

Print the number of special elements of the given array $a$.

For example, if $n=9$ and $a=[3,1,4,1,5,9,2,6,5]$, then the answer is $5$:

• $a_3=4$ is a special element, since $a_3=4=a_1+a_2=3+1$;
• $a_5=5$ is a special element, since $a_5=5=a_2+a_3=1+4$;
• $a_6=9$ is a special element, since $a_6=9=a_1+a_2+a_3+a_4=3+1+4+1$;
• $a_8=6$ is a special element, since $a_8=6=a_2+a_3+a_4=1+4+1$;
• $a_9=5$ is a special element, since $a_9=5=a_2+a_3=1+4$.

Please note that some of the elements of the array $a$ may be equal — if several elements are equal and special, then all of them should be counted in the answer.

请注意本题的内存限制为非标准限制。

为了在本题中区分高效解法与低效解法，时间限制较为严格。建议使用编译型静态类型语言（例如 C++）。若使用 Python，请提交至 PyPy 进行评测。请尽量编写高效的解法。

给定一个数组 $a=[a_1, a_2, \ldots, a_n]$（其中 $1 \le a_i \le n$）。若存在一对下标 $l$ 和 $r$（满足 $1 \le l \lt r \le n$），使得 $a_i = a_l + a_{l+1} + \ldots + a_r$，则称元素 $a_i$ 为特殊元素。换言之，若某个元素可表示为数组中两个或更多个连续元素之和（无论这些连续元素本身是否特殊），则该元素即为特殊元素。

请输出给定数组 $a$ 中特殊元素的个数。

例如，当 $n=9$、$a=[3,1,4,1,5,9,2,6,5]$ 时，答案为 $5$：

• $a_3=4$ 是特殊元素，因为 $a_3=4=a_1+a_2=3+1$；
• $a_5=5$ 是特殊元素，因为 $a_5=5=a_2+a_3=1+4$；
• $a_6=9$ 是特殊元素，因为 $a_6=9=a_1+a_2+a_3+a_4=3+1+4+1$；
• $a_8=6$ 是特殊元素，因为 $a_8=6=a_2+a_3+a_4=1+4+1$；
• $a_9=5$ 是特殊元素，因为 $a_9=5=a_2+a_3=1+4$。

请注意：数组 $a$ 中可能存在相等的元素；若多个元素值相等且均为特殊元素，则答案中应将它们全部计入。

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case is given in two lines. The first line contains an integer $n$ ($1 \le n \le 8000$) — the length of the array $a$. The second line contains integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

It is guaranteed that the sum of the values of $n$ for all test cases in the input does not exceed $8000$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示输入中测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例由两行组成。第一行包含一个整数 $n$（$1 \le n \le 8000$）—— 表示数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

保证输入中所有测试用例的 $n$ 值之和不超过 $8000$。

Print $t$ numbers — the number of special elements for each of the given arrays.

输出 $t$ 个数——即每个给定数组中特殊元素的个数。