题目描述

$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$ 行，每行一个整数，表示最少操作次数。可证明总存在一种操作满足题意。

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

3
2
0

样例解释

对于样例 $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$，显然无需操作。