Array Cloning Technique

题意翻译

你一开始有一个长度为 $n$ 的数组 $a$。你可以执行若干次操作，每次操作为如下两种中的一种： - 选择任意一个数组并新建一个和该数组完全相同的新数组。 - 交换任意两个元素。这两个元素可能是在同一个数组中，也可能是在两个不同的数组中。 你希望最终得到一个所有元素完全相同的数组，求达到这个目标的最小操作次数。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant n\leqslant 10^5$。 - $-10^9\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #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

输出样例 #1

0
6
2
5
7
0

说明

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.