Minimize the Thickness
Contest: Codeforces Round 826 (Div. 3)
Difficulty rating: 1100
Tags: brute force, greedy, math, two pointers

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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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]$$$.

Example 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

Example output:
3
4
2
3

Editorial:
Let's iterate over the length of the first segment of the split. Having fixed it, we actually fixed the sum that needs to be collected on all other segments. Since each element must belong to exactly one segment, we can build other segments greedily. If we have found a solution, we will remember the length of the longest segment in it and try to update the answer. We have $$$n$$$ possible lengths of the first segment, for each of which we greedily built the answer for $$$n$$$. Thus, the asymptotics of the solution will be $$$O(n^2)$$$.