问题说明

给定非负整数序列a₁, a₂, …, a_N。每次可以选择其中相邻的两个整数合并，合并之后的结果为这两个整数的和。请计算至少需要合并多少次，才可以让序列的所有元素一样。

例如：对于序列1, 1, 1, 3, 1, 2，选择前两个整数合并，将得到序列2, 1, 3, 1, 2；再合并前两个整数，将得到序列3, 3, 1, 2；然后合并最后两个整数，将得到序列3, 3, 3。通过3次合并，可以让序列的所有元素都为3。可以证明，对于这个序列，没有少于3次的合并方案。

输入格式

输入包含多组数据。

第一行为一个整数T（1≤T≤10），表示数据的组数。

接下来每两行描述一组输入数据：

其中第一行为一个整数N（1≤N≤10⁵且T组数据的N之和不超过10⁵），表示序列长度；

其中第二行包含N个整数a₁, a₂, …, a_N（0≤a_i≤10⁶且a_i之和不超过10⁶），表示序列的每一项元素。

输出格式

对于输入的每一组数据，输出一行一个整数，表示相应的计算结果。

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

3
0
2

来源/分类