Count Beautiful Subsegments

You are given an array of integers. A subsegment (i.e., a contiguous subarray) is called beautiful if it contains at least one nonzero element. The total number of subsegments in an array of size (n) is (\frac{n(n+1)}{2}). To compute the number of beautiful subsegments, subtract the subsegments that consist entirely of zeros. For example, consider a contiguous block of (k) zeros; it contributes (\frac{k(k+1)}{2}) subsegments that are not beautiful. Your task is to calculate the number of beautiful subsegments in each array.

Input Format: The first line of input contains a single integer (t) denoting the number of test cases. Each test case begins with an integer (n) (the size of the array) on a separate line, followed by a line with (n) space-separated integers.

Output Format: For each test case, output a single integer representing the number of beautiful subsegments.

inputFormat

The input is read from stdin as follows:

1. The first line contains an integer t: the number of test cases.
2. For each test case:
   • The first line contains an integer n, the length of the array.
   • The second line contains n space-separated integers representing the array elements.

outputFormat

For each test case, print a single integer on a new line which is the number of beautiful subsegments. The output is written to stdout.

## sample

4
3
1 2 3
3
1 0 3
3
0 0 3
4
0 0 0 0

6
5
3
0

</p>