题目描述

给定一个长度为 $N$ 的非负整数数组 $a_1, a_2, \dots, a_N$。

你可以对该数组进行若干次操作。每次操作中，你可以选择数组中任意两个相邻的元素，将它们合并为一个元素，合并后新元素的值为这两个元素之和。显然，每次操作后数组的长度会减少 $1$。

例如，如果当前数组为 $[1, 2, 3, 4, 5]$，若你选择合并第二个和第三个元素，数组将变为 $[1, 5, 4, 5]$。

请计算，为了使数组中的所有元素都相等，你最少需要进行多少次合并操作。

输入格式

第一行包含一个正整数 $T$ —— 表示测试用例的数量。

对于每组测试用例：

• 第一行包含一个正整数 $N$ —— 表示数组的长度。
• 第二行包含 $N$ 个非负整数 $a_1, a_2, \dots, a_N$ —— 表示数组中的元素。

输出格式

对于每组测试用例，输出一行一个整数，表示使数组中所有元素相等所需的最少操作次数。

样例输入 1

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

样例输出 1

3
2
0

说明

样例解释

• 在第一个测试用例中，可以通过 $3$ 次合并操作将数组变为全 $3$： $[1, 2, 3, 1, 1, 1] \to [3, 3, 1, 1, 1] \to [3, 3, 2, 1] \to [3, 3, 3]$。
• 在第二个测试用例中，可以通过 $2$ 次合并操作将数组变为全 $7$： $[2, 2, 3] \to [2, 5] \to [7]$。
• 在第三个测试用例中，不需要进行任何操作，因为数组原本就已经由相同的数字组成。

数据范围

• 对于所有测试点，保证 $1 \le T \le 10^3$。
• 对于每组测试用例，保证 $1 \le N \le 10^5$。
• 对于每组测试用例，保证 $0 \le a_i \le 10^6$。
• 保证每组测试用例中，数组元素之和（即 $\sum a_i$）不超过 $10^6$。
• 保证同一测试点内所有测试用例的 $N$ 之和不超过 $10^5$。
• 保证所有的输入数值均为整数。