CF1665B.Array Cloning Technique

You are given an array $a$ of $n$ integers. Initially there is only one copy of the given array.

You can do operations of two types:

1. Choose any array and clone it. After that there is one more copy of the chosen array.
2. Swap two elements from any two copies (maybe in the same copy) on any positions.

You need to find the minimal number of operations needed to obtain a copy where all elements are equal.

给你一个包含 $n$ 个整数的数组 $a$。初始时，仅存在该数组的一个副本。

你可以执行以下两种操作：

1. 任选一个数组并将其复制（克隆）。执行后，所选数组的副本数量增加一个。
2. 从任意两个副本（可能为同一副本）中任选两个元素，并交换它们（可在任意位置上进行）。

你需要求出：使得某个副本中所有元素均相等所需的最少操作次数。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case output a single integer — the minimal number of operations needed to create at least one copy where all elements are equal.

对于每个测试用例，输出一个整数——创建至少一个所有元素均相等的副本所需的最少操作次数。

In the first test case all elements in the array are already equal, that's why the answer is $0$.

In the second test case it is possible to create a copy of the given array. After that there will be two identical arrays:

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

After that we can swap elements in a way so all zeroes are in one array:

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

Now let's create a copy of the first array:

$[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$, $[ \ 0 \ 0 \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$

Let's swap elements in the first two copies:

$[ \ 0 \ 0 \ 0 \ \underline{0} \ \underline{0} \ 0 \ ]$, $[ \ \underline{3} \ \underline{7} \ 0 \ 3 \ 7 \ 0 \ ]$ and $[ \ 1 \ 1 \ 3 \ 3 \ 7 \ 3 \ ]$.

Finally, we made a copy where all elements are equal and made $6$ operations.

It can be proven that no fewer operations are enough.

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

在第二个测试用例中，可以创建给定数组的一个副本。此后将存在两个完全相同的数组：

$[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 0 \ ]$ 和 $[ \ 0 \ 1 \ 3 \ 3 \ 7 \ 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$ 次操作。

可以证明：不存在少于 $6$ 次操作的可行方案。