题目描述

给定一个长度为 $n$ 的整数数组 $a$。最初只有一份该数组的副本。

你可以进行两种操作：

1. 选择任意一个数组并克隆它。此后，该数组的副本数量加一。
2. 在任意两个副本（可以是同一个副本）中的任意位置交换两个元素。

你需要求出，最少需要多少次操作，才能得到一个所有元素都相等的副本。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数，表示最少需要多少次操作，才能得到一个所有元素都相等的副本。

说明/提示

在第一个测试用例中，数组的所有元素已经相等，因此答案为 $0$。

在第二个测试用例中，可以先克隆一次原数组，此时有两个相同的数组：

$[0\ 1\ 3\ 3\ 7\ 0]$ 和 $[0\ 1\ 3\ 3\ 7\ 0]$

然后可以交换元素，使得所有的 $0$ 都在一个数组中：

$[0\ \underline{0}\ \underline{0}\ 3\ 7\ 0]$ 和 $[\underline{1}\ 1\ 3\ 3\ 7\ \underline{3}]$

接着克隆第一个数组：

$[0\ 0\ 0\ 3\ 7\ 0]$，$[0\ 0\ 0\ 3\ 7\ 0]$ 和 $[1\ 1\ 3\ 3\ 7\ 3]$

再交换前两个副本中的元素：

$[0\ 0\ 0\ \underline{0}\ \underline{0}\ 0]$，$[\underline{3}\ \underline{7}\ 0\ 3\ 7\ 0]$ 和 $[1\ 1\ 3\ 3\ 7\ 3]$

最终，我们得到了一个所有元素都相等的副本，总共进行了 $6$ 次操作。

可以证明，不可能用更少的操作完成。

由 ChatGPT 4.1 翻译

样例

6
1
1789
6
0 1 3 3 7 0
2
-1000000000 1000000000
4
4 3 2 1
5
2 5 7 6 3
7
1 1 1 1 1 1 1

0
6
2
5
7
0