CF1741C.Minimize the Thickness

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.

给你一个由 $n$ 个正整数组成的序列 $a=[a_1,a_2,\dots,a_n]$。

我们将连续元素组成的子序列称为段（segment）。每个段由两个下标刻画：左端点下标与右端点下标。记 $a[l,r]$ 为序列 $a$ 中左端点为 $l$、右端点为 $r$ 的段，即 $a[l,r]=[a_l, a_{l+1}, \dots, a_r]$。

例如，若 $a=[31,4,15,92,6,5]$，则 $a[2,5]=[4,15,92,6]$，$a[5,5]=[6]$，$a[1,6]=[31,4,15,92,6,5]$ 均为段。

我们需将给定序列 $a$ 划分为若干段，使得：

• 每个元素恰好属于一个段；
• 所有段的元素之和均相等。

例如，若 $a = [55,45,30,30,40,100]$，则该序列可划分为三个段：$a[1,2]=[55,45]$，$a[3,5]=[30, 30, 40]$，$a[6,6]=[100]$。每个元素恰好属于一个段，且每段元素之和均为 $100$。

我们定义该划分的**厚度（thickness）**为所有段中最长段的长度。例如，上述例子中划分的厚度为 $3$。

请找出在满足上述条件的所有可能划分中，最小的厚度值。

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

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 测试用例的数量。

每个测试用例由两行描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）—— 序列 $a$ 的长度。

每个测试用例的第二行包含恰好 $n$ 个整数：$a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）—— 序列 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，输出一个整数——将序列 $a$ 分割为若干段时可能的最小厚度。

注意：这样的分割总是存在的，你可以始终将整个序列视为一段。

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

第一个测试用例中的分割方式在题面中已作解释，可以证明该分割是最优的。

第二个测试用例中，仅能将序列划分为一个单独的段。此时该分割的厚度等于整个序列的长度，即 $4$。

第三个测试用例中，最优分割为 $[10, 55], [35, 30], [65]$，该分割的厚度为 $2$。

第四个测试用例中，可能的分割方式有：

• $[4] + [1, 1, 1, 1] + [4]$；
• $[4, 1, 1] + [1, 1, 4]$。