[Solution] Minimize the Thickness Codeforces Solution

C. Minimize the Thickness

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence 𝑎=[𝑎1,𝑎2,…,𝑎𝑛]$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. 𝑎[𝑙,𝑟]=[𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟]$a[l,r]=[a_l,a_{l+1},\dots ,a_r]$.

For example, if 𝑎=[31,4,15,92,6,5]$a=[31,4,15,92,6,5]$, then 𝑎[2,5]=[4,15,92,6]$a[2,5]=[4,15,92,6]$, 𝑎[5,5]=[6]$a[5,5]=[6]$, 𝑎[1,6]=[31,4,15,92,6,5]$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$55,45,30,30,40,100$], then such a sequence can be split into three segments: 𝑎[1,2]=[55,45]$a[1,2]=[55,45]$, 𝑎[3,5]=[30,30,40]$a[3,5]=[30,30,40]$, 𝑎[6,6]=[100]$a[6,6]=[100]$. Each element belongs to exactly segment, the sum of the elements of each segment is 100$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$3$.

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

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤100$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≤𝑛≤2000$1\le n\le 2000$) — the length of the sequence 𝑎$a$.

The second line of each test case contains exactly 𝑛$n$ integers: 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤106$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$2000$.

Output

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.