题目描述

给你一个长度为 $n$ 的数组 $a$，第 $i$ 个元素为 $a_i$。我们可以将 $a$ 分为若干个连续的不为空的子段，但前提条件是每个元素都要在一个子段里，且每个子段里的元素和都必须相等。

例如，我们有一个长度为 $6$ 的数组 $[55,45,30,30,40,100]$，如果我们把这个数组分为 $[55,45]$、$[30,30,40]$ 和 $[100]$ 三个子段的话，那么每个子段里的元素和都为 $100$。

定义若干个子段的厚度为这些子段里元素最多的子段里的元素个数，你的目标就是给定一个长度为 $n$ 的数组，找到一种分割子段的方法，使得分割后所有子段的厚度最小。

输入格式

第一行，一个正整数 $t(1 \leq t \leq 100)$，表示数据组数。

每组输入由两行组成：

第一行是一个正整数 $n(1 \leq n \leq 2000)$，表示数组的长度。

第二行，$n$ 个正整数，表示你需要分割的数组。

数据保证 $\sum n \leq 2000$。

输出格式

对于每一组数据，输出一个正整数，表示可以得到的最小厚度。

（Translated by

样例

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

3
4
2
3