You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
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).

## Input Format
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$$$.

## Output Format
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).

## Examples
```input
4
5
3 1 6 6 2
4
1 2 2 1
3
2 2 2
4
6 3 2 1
```
```output
4
2
0
2
```

## Note
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.

Now solve the problem and return the code.