Problem C: 相同数列

Memory Limit:128 MB Time Limit:3.000 S
Creator:
Submit:36 Solved:6

Description

又话说正当轩轩要带走这些硬币的时候,石门突然又关上了,一道题目出现在了石门上。轩轩慌了手脚,正当他害怕之时,他突然又想到了聪明伶俐善良大方的你,请你写一个程序帮他解开谜题。
石板上出现了一串数字,你可以做两种操作: 
1 任意选择一个数列进项复制 
2从任意位置的任意两个数列(可能在同一数列中)交换两个元素。 在所有元素相等的情况下,需要找到获得数列所需的最小操作数。

Input

第一行包含一个整数t(1≤T≤10^4)-测试中的测试用例数 
每个测试用例的第一行包含一个整数n(1≤n≤10^5)-数组a的长度。
每个测试用例的第二行包含n个整数a1、a2、…、an(−10^9≤ai≤10^9)数组a的元素。 
保证所有测试用例中n的总和不超过10^5。

Output

对于每个测试用例输出一个整数——在所有元素相等的情况下创建至少一个数列所需的最小操作数。

Sample Input

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

Sample Output

0
6
2
5
7
0

HINT

在第一个数列中,数组中的所有元素都已经相等,这就是为什么答案是0

第二个数列可以先进行一次复制。之后会u有两个相同的数列:

[ 0 1 3 3 7 0 ] [ 0 1 3 3 7 0 ]

然后,我们可以交换元素,使所有零都在一个数组中:

[ 0 0 0 3 7 0 ] 和 [ 1 1 3 3 7 3 ]

现在,让我们复制第一个数列:

[ 0 0 0 3 7 0 ], [ 0 0 0 3 7 0 ] [ 1 1 3 3 7 3 ]

然后,我们可以交换元素,使所有零都在一个数组中:

[ 0 0 0 0 0 0 ], [ 3 7 0 3 7 0 ] [ 1 1 3 3 7 3 ].

最后,我们制作了一个所有元素都相等的数列,并进行了6次操作。

【数据范围限制】

对于30%的数据T < 10 ni < 10

对于100%的数据 1n10^5  10^9ai10^9