Add to Neighbour and Remove

题意翻译

给定一个长度为 $n$ 的序列 $a$。 现在你可以进行若干次合并操作，每次操作选定两个相邻的数，然后把这两个数合并成一个数。 换句话说，每次选定一个整数 $i(1\leq i<|a|)$，然后删除 $a_i,a_{i+1}$，把 $a_i+a_{i+1}$ 插入到序列 $a$ 的位置 $i$ 上，这样序列 $a$ 的长度就会减一。 现在你要使这个序列所有元素相同，求操作数最小值。 比如当 $n=4,a=\{1,2,3,6\}$ 时，我们可以： - 合并 $a_1,a_2$，序列变为 $\{3,3,6\}$。 - 合并 $a_1,a_2$，序列变为 $\{6,6\}$。 答案就是 $2$。 $T$ 组询问。 $1\leq n\leq3\times 10^3,\sum n\leq3\times10^3.$ 初始时 $1\leq a_i\leq 10^5.$

题目描述

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

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #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

说明

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.