B. Smartass (Easy Version) - Yellow
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aboud and Fakher the League addicts were playing 2v2v2v2. Fakher absolutely hates it when Aboud goes full AP Nunu so he decided to make a deal with him this time. If Aboud can solve this problem then he'll let him go full AP Nunu for the rest of the day. Can you help Aboud fulfill his dream?

This is the easy version of the problem. The only difference between the easy and hard version is the constraint on $$$n$$$

You are given an array $$$a$$$ of length $$$n$$$ consisting of integers

A subarray $$$a_l,a_{l+1},…,a_r$$$ is good if it isn't empty and the sum of elements of this subarray is zero $$$(\sum_{i=l}^{r} a_i = 0)$$$

Calculate the number of good subarrays in the array $$$a$$$

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1≤t≤10^3)$$$ — the number of test cases

The first line of each test case contains an integer $$$n$$$ $$$(1≤n≤10^3)$$$ — the length of the array

The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(-10^9≤a_i≤10^9)$$$ — the elements of the array $$$a$$$

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$

Output

Print $$$t$$$ lines, each line containing the answer to the corresponding test case — the number of good subarrays in the array $$$a$$$

Example
Input
4
1
0
3
1 -1 0
5
1 2 3 4 5
10
1 2 3 -3 0 -2 -1 0 0 3
Output
1
3
0
13