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.

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

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.