Polycarp 被赋予了 $$$a[1 \dots n]$$$ 的 $$$n$$$ 整数数组。他可以对数组 $$$a$$$ 执行以下操作不超过 $$$n$$$ 次:
- Polycarp 选择索引 $$$i$$$ 并将值 $$$a_i$$$ 添加到他选择的邻居之一。更正式地说,Polycarp 将 $$$a_i$$$ 的值添加到 $$$a_{i-1}$$$ 或 $$$a_{i+1}$$$ (如果这样的邻居不存在,则不可能添加到它)。
- 添加后,Polycarp 从 $$$a$$$ 数组中删除第 $$$i$$$ 个元素。在此步骤中,$$$a$$$ 的长度减少 $$$1$$$。
以上两项一起表示一项操作。
例如,如果 Polycarp 有一个数组 $$$a = [3, 1, 6, 6, 2]$$$,那么它可以用它执行以下操作序列:
- Polycarp 选择 $$$i = 2$$$ 并将值 $$$a_i$$$ 添加到 $$$(i-1)$$$ 第一个元素:$$$a = [4, 6, 6, 2]$$$。
- Polycarp 选择 $$$i = 1$$$ 并将值 $$$a_i$$$ 添加到 $$$(i+1)$$$ 第一个元素:$$$a = [10, 6, 2]$$$。
- Polycarp 选择 $$$i = 3$$$ 并将值 $$$a_i$$$ 添加到第 $$$(i-1)$$$ 个元素:$$$a = [10, 8]$$$。
- Polycarp 选择 $$$i = 2$$$ 并将值 $$$a_i$$$ 添加到第 $$$(i-1)$$$ 元素:$$$a = [18]$$$。
请注意,Polycarp 可以随时停止执行操作。
Polycarp 想知道他需要执行多少次最小操作才能使 $$$a$$$ 的所有元素相等(即,他希望所有 $$$a_i$$$ 彼此相等)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3000$$$) — 测试中的测试用例数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3000$$$) — 数组的长度。下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — 数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,输出一个数字 - Polycarp 需要执行的最小操作数,以便 $$$a$$$ 数组的所有元素都相同(相等)。
示例
输入 #1
4 5 3 1 6 6 2 4 1 2 2 1 3 2 2 2 4 6 3 2 1
输出 #1
4 2 0 2
注意
在示例的第一个测试用例中,答案可以这样构造(只是许多其他方法中的一种方法):
$$$[3, 1, 6, 6, 2]$$$ $$$\xrightarrow[]{i=4,~add~to~left}$$$ $$$[3, 1, 12, 2]$$$ $$$\xrightarrow[]{i=2,~add~to~right}$$$ $$$[3, 13, 2]$$$ $$$\xrightarrow[]{i=1,~添加~到~右}$$$ $$$[16, 2]$$$ $$$\xrightarrow[]{i=2,~添加~到~左}$$$ $$$[18]$$$。数组 $$$[18]$$$ 的所有元素都相同。
在示例的第二个测试用例中,答案可以这样构造(只是其他方式中的一种方式):
$$$[1, 2, 2, 1]$$$ $$$\xrightarrow[]{i=1,~add~to~right}$$$ $$$[3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~add~to~left}$$$ $$$[3, 3]$$$。数组 $$$[3, 3]$$$ 的所有元素都相同。
在示例的第三个测试用例中,Polycarp 不需要执行任何操作,因为 $$$[2, 2, 2]$$$ 仅包含相等(相同)的元素。
在示例的第四个测试用例中,答案可以这样构造(只是其他方式中的一种方式):
$$$[6, 3, 2, 1]$$$ $$$\xrightarrow[]{i=3,~add~to~right}$$$ $$$[6, 3, 3]$$$ $$$\xrightarrow[]{i=3,~add~to~left}$$$ $$$[6, 6]$$$。数组 $$$[6, 6]$$$ 的所有元素都相同。