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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a sequence $$$a=[a_1,a_2,\dots,a_n]$$$ consisting of $$$n$$$ positive integers.

Let's call a group of consecutive elements a segment. Each segment is characterized by two indices: the index of its left end and the index of its right end. Denote by $$$a[l,r]$$$ a segment of the sequence $$$a$$$ with the left end in $$$l$$$ and the right end in $$$r$$$, i.e. $$$a[l,r]=[a_l, a_{l+1}, \dots, a_r]$$$.

For example, if $$$a=[31,4,15,92,6,5]$$$, then $$$a[2,5]=[4,15,92,6]$$$, $$$a[5,5]=[6]$$$, $$$a[1,6]=[31,4,15,92,6,5]$$$ are segments.

We split the given sequence $$$a$$$ into segments so that:

- each element is in exactly one segment;
- the sums of elements for all segments are equal.

For example, if $$$a$$$ = [$$$55,45,30,30,40,100$$$], then such a sequence can be split into three segments: $$$a[1,2]=[55,45]$$$, $$$a[3,5]=[30, 30, 40]$$$, $$$a[6,6]=[100]$$$. Each element belongs to exactly segment, the sum of the elements of each segment is $$$100$$$.

Let's define thickness of split as the length of the longest segment. For example, the thickness of the split from the example above is $$$3$$$.

Find the minimum thickness among all possible splits of the given sequence of $$$a$$$ into segments in the required way.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case is described by two lines.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the length of the sequence $$$a$$$.

The second line of each test case contains exactly $$$n$$$ integers: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — elements of the sequence $$$a$$$.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2000$$$.

## Output Format
For each test case, output one integer — the minimum possible thickness of a split of the sequence $$$a$$$ into segments.

Note that there always exist a split, you can always consider whole sequence as one segment.

## Examples
```input
4
6
55 45 30 30 40 100
4
10 23 7 13
5
10 55 35 30 65
6
4 1 1 1 1 4
```
```output
3
4
2
3
```

## Note
The split in the first test case is explained in the statement, it can be shown that it is optimal.

In the second test case, it is possible to split into segments only by leaving a single segment. Then the thickness of this split is equal to the length of the entire sequence, that is, $$$4$$$.

In the third test case, the optimal split will be $$$[10, 55], [35, 30], [65]$$$. The thickness of the split equals to $$$2$$$.

In the fourth test case possible splits are:

- $$$[4] + [1, 1, 1, 1] + [4]$$$;
- $$$[4, 1, 1] + [1, 1, 4]$$$.

Now solve the problem and return the code.