给定一个序列 $$$a=[a_1,a_2,\dots,a_n]$$$,由 $$$n$$$ 正整数组成。
让我们将一组连续元素称为段。每个段都有两个索引:其左端索引和右端索引。用 $$$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$$$。
让我们将分割的厚度定义为最长线段的长度。例如,上例中分割的厚度为 $$$3$$$。
求出给定序列 $$$a$$$ 按要求的方式分割成段的所有可能分割中的最小厚度。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 将序列 $$$a$$$ 分割成段的最小可能厚度。
请注意,始终存在分割,您始终可以将整个序列视为一个片段。
示例
输入 #1
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
输出 #1
3 4 2 3
注意
第一个测试用例中的分割在语句中进行了解释,可以证明它是最优的。
在第二个测试用例中,可以仅通过留下单个段来分割成段。那么这个分割的厚度就等于整个序列的长度,即$$$4$$$。
在第三个测试用例中,最佳分割将为 $$$[10, 55], [35, 30], [65]$$$。裂缝的厚度等于$$$2$$$。
在第四个测试用例中,可能的拆分是:
- $$$[4] + [1, 1, 1, 1] + [4]$$$;
- $$$[4, 1, 1] + [1, 1, 4]$$$.