## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 $a=\left[{a}_{1},{a}_{2},\dots ,{a}_{n}\right]$ 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\left[l,r\right]$ a segment of the sequence $a$ with the left end in $l$ and the right end in $r$, i.e. $a\left[l,r\right]=\left[{a}_{l},{a}_{l+1},\dots ,{a}_{r}\right]$.

For example, if $a=\left[31,4,15,92,6,5\right]$, then $a\left[2,5\right]=\left[4,15,92,6\right]$$a\left[5,5\right]=\left[6\right]$$a\left[1,6\right]=\left[31,4,15,92,6,5\right]$ 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\left[1,2\right]=\left[55,45\right]$$a\left[3,5\right]=\left[30,30,40\right]$$a\left[6,6\right]=\left[100\right]$. 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

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

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.