题目描述

有 $N$ 堆石子，每堆的石子数量分别为 $a_1,a_2 \dots a_N$。

你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。

我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。

请你输出所需的最少操作次数。

本题一定有解，因为可以将所有石子堆合并为一堆。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $N$。

第二行包含 $N$ 个整数 $a_1,a_2\dots a_N$。

输出格式

每组数据输出一行结果。

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

3
2
0

提示

$1≤T≤10,$
$1≤N≤10^5,$
$0≤a_i≤10^6,$
$\sum_{k=1}^n a_i≤10^6$,
每个输入所有 $N$ 之和不超过 $10^5$。

样例解释

第一组数据，只需要用 3 个操作来完成：

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

第二组数据，只需要用 2 个操作来完成：

2 2 3
-> 2 5
-> 7

第三组数据，我们什么都不需要做。