You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let there be an array $$$b_1, b_2, \ldots, b_k$$$. Let there be a partition of this array into segments $$$[l_1; r_1], [l_2; r_2], \ldots, [l_c; r_c]$$$, where $$$l_1 = 1$$$, $$$r_c = k$$$, and for any $$$2 \leq i \leq c$$$ holds that $$$r_{i-1} + 1 = l_i$$$. In other words, each element of the array belongs to exactly one segment.

Let's define the cost of a partition as $$$$$$c + \sum_{i = 1}^{c} \operatorname{mex}(\{b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\}),$$$$$$ where $$$\operatorname{mex}$$$ of a set of numbers $$$S$$$ is the smallest non-negative integer that does not occur in the set $$$S$$$. In other words, the cost of a partition is the number of segments plus the sum of MEX over all segments. Let's define the value of an array $$$b_1, b_2, \ldots, b_k$$$ as the maximum possible cost over all partitions of this array.

You are given an array $$$a$$$ of size $$$n$$$. Find the sum of values of all its subsegments.

An array $$$x$$$ is a subsegment of an array $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
The input contains several test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 30$$$) — the number of test cases.

The first line for each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the array.

The second line contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the array elements.

It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$100$$$.

## Output Format
For each test case print a single integer — the answer to the problem.

## Examples
```input
4
2
1 2
3
2 0 1
4
2 0 5 1
5
0 1 1 0 1
```
```output
4
14
26
48
```

## Note
In the second test case:

- The best partition for the subsegment $$$[2, 0, 1]$$$: $$$[2], [0, 1]$$$. The cost of this partition equals to $$$2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0, 1\}) = 2 + 0 + 2 = 4$$$.
- The best partition for the subsegment $$$[2, 0]$$$: $$$[2], [0]$$$. The cost of this partition equals to $$$2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0\}) = 2 + 0 + 1 = 3$$$
- The best partition for the subsegment $$$[2]$$$: $$$[2]$$$. The cost of this partition equals to $$$1 + \operatorname{mex}(\{2\}) = 1 + 0 = 1$$$.
- The best partition for the subsegment $$$[0, 1]$$$: $$$[0, 1]$$$. The cost of this partition equals to $$$1 + \operatorname{mex}(\{0, 1\}) = 1 + 2 = 3$$$.
- The best partition for the subsegment $$$[0]$$$: $$$[0]$$$. The cost of this partition equals to $$$1 + \operatorname{mex}(\{0\}) = 1 + 1 = 2$$$.
- The best partition for the subsegment $$$[1]$$$: $$$[1]$$$. The cost of this partition equals to $$$1 + \operatorname{mex}(\{1\}) = 1 + 0 = 1$$$.

The sum of values over all subsegments equals to $$$4 + 3 + 1 + 3 + 2 + 1 = 14$$$.

Now solve the problem and return the code.