CF1462D.Add to Neighbour and Remove

Polycarp was given an array of $a[1 \dots n]$ of $n$ integers. He can perform the following operation with the array $a$ no more than $n$ times:

• Polycarp selects the index $i$ and adds the value $a_i$ to one of his choice of its neighbors. More formally, Polycarp adds the value of $a_i$ to $a_{i-1}$ or to $a_{i+1}$ (if such a neighbor does not exist, then it is impossible to add to it).
• After adding it, Polycarp removes the $i$-th element from the $a$ array. During this step the length of $a$ is decreased by $1$.

The two items above together denote one single operation.

For example, if Polycarp has an array $a = [3, 1, 6, 6, 2]$, then it can perform the following sequence of operations with it:

• Polycarp selects $i = 2$ and adds the value $a_i$ to $(i-1)$-th element: $a = [4, 6, 6, 2]$.
• Polycarp selects $i = 1$ and adds the value $a_i$ to $(i+1)$-th element: $a = [10, 6, 2]$.
• Polycarp selects $i = 3$ and adds the value $a_i$ to $(i-1)$-th element: $a = [10, 8]$.
• Polycarp selects $i = 2$ and adds the value $a_i$ to $(i-1)$-th element: $a = [18]$.

Note that Polycarp could stop performing operations at any time.

Polycarp wondered how many minimum operations he would need to perform to make all the elements of $a$ equal (i.e., he wants all $a_i$ are equal to each other).

波利卡普得到了一个包含 $n$ 个整数的数组 $a[1 \dots n]$。他最多可对数组 $a$ 执行 $n$ 次如下操作：

• 波利卡普选择一个下标 $i$，并将 $a_i$ 的值加到其某个相邻元素上。更准确地说，波利卡普将 $a_i$ 的值加到 $a_{i-1}$ 或 $a_{i+1}$ 上（若该相邻位置不存在，则无法执行此加法）。
• 加法完成后，波利卡普从数组 $a$ 中删除第 $i$ 个元素。此步骤使数组 $a$ 的长度减少 $1$。

以上两个步骤共同构成一次完整操作。

例如，若波利卡普拥有数组 $a = [3, 1, 6, 6, 2]$，则可对其执行如下操作序列：

• 波利卡普选择 $i = 2$，并将 $a_i$ 的值加到第 $(i-1)$ 个元素上：$a = [4, 6, 6, 2]$。
• 波利卡普选择 $i = 1$，并将 $a_i$ 的值加到第 $(i+1)$ 个元素上：$a = [10, 6, 2]$。
• 波利卡普选择 $i = 3$，并将 $a_i$ 的值加到第 $(i-1)$ 个元素上：$a = [10, 8]$。
• 波利卡普选择 $i = 2$，并将 $a_i$ 的值加到第 $(i-1)$ 个元素上：$a = [18]$。

注意：波利卡普可在任意时刻停止执行操作。

波利卡普想知道：为使数组 $a$ 中所有元素相等（即所有 $a_i$ 彼此相等），他至少需要执行多少次操作？

The first line contains a single integer $t$ ($1 \leq t \leq 3000$) — the number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 3000$) — the length of the array. The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

第一行包含一个整数 $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$。

For each test case, output a single number — the minimum number of operations that Polycarp needs to perform so that all elements of the $a$ array are the same (equal).

对于每个测试用例，输出一个整数——Polycarp 需要执行的最少操作次数，使得数组 $a$ 的所有元素都相同（相等）。

In the first test case of the example, the answer can be constructed like this (just one way among many other ways):

$[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,~add~to~right}$ $[16, 2]$ $\xrightarrow[]{i=2,~add~to~left}$ $[18]$. All elements of the array $[18]$ are the same.

In the second test case of the example, the answer can be constructed like this (just one way among other ways):

$[1, 2, 2, 1]$ $\xrightarrow[]{i=1,~add~to~right}$ $[3, 2, 1]$ $\xrightarrow[]{i=3,~add~to~left}$ $[3, 3]$. All elements of the array $[3, 3]$ are the same.

In the third test case of the example, Polycarp doesn't need to perform any operations since $[2, 2, 2]$ contains equal (same) elements only.

In the fourth test case of the example, the answer can be constructed like this (just one way among other ways):

$[6, 3, 2, 1]$ $\xrightarrow[]{i=3,~add~to~right}$ $[6, 3, 3]$ $\xrightarrow[]{i=3,~add~to~left}$ $[6, 6]$. All elements of the array $[6, 6]$ are the same.

在示例的第一个测试用例中，答案可以如下构造（这只是众多可行方式中的一种）：

$[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,~add~to~right}$ $[16, 2]$ $\xrightarrow[]{i=2,~add~to~left}$ $[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]$ 的所有元素均相同。