解题思路

• 我们把每次“相邻合并”看作把数组切成若干段、每段内部合并成一个数（为该段元素和）。
• 若最终都相等，则必然能把数组划分为连续的 $K$ 段，每段和均为同一个值 $S$，且总和 $\text{SUM}=\sum a_i=K\cdot S$。
• 操作次数 = 初始长度 $n$ 减去剩余段数 $K$：最少操作数 $= n-K$。因此问题转化为：最大化可行的段数 $K$。

关键观察：

1. 第一段是一个前缀，所以段和 $S$ 必为某个前缀和；

题目内容

多多有一个长度为 $n$ 从左到右依次排列的数组 $a_1,a_2,...,a_n$ 。

多多可以对这个数组进行任意次操作,每次操作可以选择数组中两个相邻的数，把它们合并成一个新数(新数的值为两数之和)，合并后数组长度减少 $1$ .

多多想知道，最少需要多少次这样的操作，才能让数组中所有数都相等

输入描述

第一行,包含一个正整数 $T(1 ≤T≤3)$ 代表测试数据的组数

对于每组测试数据,分别有两行:

第一行,仅有一个正整数 $n(1 ≤n≤ 10^5)$

第二行,包含 $n$ 个正整数,分别表示 $a_1,a_2,...,a_n(1≤a_i ≤ 10^9)$

输出描述

对每组测试，输出一个整数，表示使所有剩余数字相等所需的最少操作次数.

样例1

输入

2
4
2 3 3 2
4
10 9 8 7

输出

2
3

说明

对于第一组数据,可以在两次合并操作后,变为数组 $[5,5]$

对于第二组数据,可以在三次合并操作后,变为数组 $[34]$