C. End-Balanced Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. A sub-array $$$[a_l, a_{l+1}, \cdots a_r]$$$ is considered end-balanced if $$$l \lt r$$$ and $$$a_l + a_r = a_{l+1} + ... + a_{r-1}$$$.

For example, the subarrays $$$[4, 9, 5]$$$, $$$[-1, 3, 5, 9]$$$, and $$$[0, 0]$$$ are considered end-balanced, and the subarrays $$$[0]$$$, $$$[-2, -3, -5]$$$, and $$$[1, 1]$$$ are not.

How many subarrays of $$$a$$$ are end-balanced?

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2 \cdots a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print a single integer — the number of end-balanced subarrays of $$$a$$$.

Example
Input
7
5
1 2 3 4 5
3
0 0 0
4
-10 5 -5 10
6
2 2 2 2 2 2
7
1 0 1 0 1 0 1
5
1000000000 1000000000 1000000000 1000000000 1000000000
1
-1000000000
Output
2
3
2
3
5
2
0
Note

The end-balanced subarrays in the first test case are:

  • $$$[a_1, a_2, a_3, a_4] = [1, 2, 3, 4]$$$
  • $$$[a_2, a_3, a_4, a_5] = [2, 3, 4, 5]$$$

The end-balanced subarrays in the second test case are:

  • $$$[a_1, a_2] = [0, 0]$$$
  • $$$[a_2, a_3] = [0, 0]$$$
  • $$$[a_1, a_2, a_3] = [0, 0, 0]$$$

The end-balanced subarrays in the third test case are:

  • $$$[a_2, a_3] = [5, -5]$$$
  • $$$[a_1, a_2, a_3, a_4] = [-10, 5, -5, 10]$$$