题目描述

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often. Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are $N$ class periods $(1\le N\le 10^5)$, and Elsie logs that Bessie fell asleep $a_i$ times $(0\le a_i\le 10^6)$ in the $i$-th class period. The total number of times Bessie fell asleep across all class periods is at most $10^6$.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures. The only way Elsie may modify the log is by combining two adjacent class periods. For example, if $a=[1,2,3,4,5]$, then if Elsie combines the second and third class periods the log will become $[1,5,4,5]$.

Help Elsie compute the minimum number of modifications to the log that she needs to make so that she can make all the numbers in the log equal.

输入格式

Each input will contain $T$ $(1\le T\le 10)$ test cases that should be solved independently.

The first line contains $T$, the number of test cases to be solved. The $T$ test cases follow, each described by a pair of lines. The first line of each pair contains $N$, and the second contains $a_1,a_2,\ldots,a_N$.

It is guaranteed that within each test case, the sum of all values in $a$ is at most $10^6$. It is also guaranteed that the sum of $N$ over all test cases is at most $10^5$.

输出格式

Please write $T$ lines of output, giving the minimum number of modifications Elsie could perform to make all the log entries equal for each case.

题目大意

$T$ 组数据，每组给定一个长度为 $N$ 的数组 $a_1, a_2, \dotsb , a_n$。

每次操作可选择两个相邻的数合并，得到的新数为两者之和。

求最少操作次数使得所有数相等。

数据范围： $1 \leq T \leq 10$，$\sum a_i \leq 10^6$，$\sum N \leq 10^5$，$1 \le T \le 10$。

【输入格式】

一行一个整数 $T$。

接下来 $T$ 组数据，每组数据第一行一个整数 $N$，第二行 $N$ 个整数，$a_1, a_2, \dotsb , a_n$，含义如题目描述。

【输出格式】

$T$ 行，每行一个整数，表示最少操作次数。可证明总存在一种操作满足题意。

【样例解释】

对于样例 $1$，显然可以通过如下 $3$ 次操作将原序列变成 3 3 3：

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

对于样例 $2$，显然可以通过如下 $2$ 次操作将原序列变成 7：

   2 2 3
-> 2 5
-> 7

对于样例 $3$，显然无需操作。

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

3
2
0

提示

【样例解释】

For the first test case in this example, Elsie can change her log to consist solely of 3s with 3 modifications.

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

For the second test case, Elsie can change her log to 7 with 2 modifications.

   2 2 3
-> 2 5
-> 7

For the last test case, Elsie doesn’t need to perform any operations; the log already consists of equal entries.