样例下载

题目描述

有 $N$ 个整数排成一排，第 $i$ 个整数为 $X_i$。

你可以进行以下操作：

任意选择相邻的两个整数进行合并，用它们的和代替原先的两个整数。

你可以操作任意次。

你的目标是：最后得到若干个相同的整数。

问：你最少需要操作多少次？

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：一个整数 $N$
• 第二行：$N$ 个整数 $X_i$

输出格式

共 $T$ 行，每组数据的答案占一行。

输入样例

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

输出样例

0
2
3

样例解释

第一组数据：两个整数本来就相同，无需操作。

第二组数据：两次操作，最后得到一个整数 5。

第三组数据：三次操作，以下是一种可能的操作方案：

• 第一次操作：[1+1=2] 1 1 2 3

• 第二次操作：[2+1=3] 1 2 3

• 第三次操作：3 [1+2=3] 3

最后得到三个 3

数据范围

10% 的数据：$1 ≤ N ≤ 10$；

20% 的数据：$1 ≤ N ≤ 100$；

40% 的数据：$1 ≤ N ≤ 1000$；

100% 的数据：$1 ≤ T ≤ 10$, $1 ≤ N ≤ 10^5$, $0 ≤ X_i ≤ 10^6$, 数据保证所有组数据中的 $\sum N ≤ 10^5$, 每组数据中的 $\sum X_i ≤ 10^6$。