1468: 重铸坎瑞亚荣光

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:137 Solved:43

Description

“那一场大战,坎瑞亚变成了废墟,人民饱受诅咒之苦。这些年,我饱食仇恨与不甘。我也该担起我的使命了——重铸坎瑞亚荣光。“荧如是说。

“公主殿下,我们正在研发的新型战斗机器人研发出现了瓶颈。”深渊咏者.紫电弓身说道。

“我们现在有一个长度为n的数组,我们需要通过最少的特定的操作,使得数组中的全部数字变为一样的数字。”深渊使徒.激流补充道。

“特定的操作?”荧抬眼望向深渊使徒.激流。

有两种操作:第一种是选择一个数组进行复制,这样你就会获得一个新的同样的数组;第二种操作是选择两个分别来自于不同数组的数字,对它们进行交换。

“交给我吧,这是我无法逃脱的命运。”荧目光如炬。

Input

输入由t(1<=t<=100)个样例组成,每个样例包含两行。

第一行是一个整数n(1<=n<=1e5),代表整数数组的长度。

第二行是a0....an-1(-1e9<=ai<=1e9),代表数组中每个数字。

Output

输出共包含t行。

每一行包括一个数字Si,代表样例i最少的操作次数。

Sample Input Copy

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

Sample Output Copy

6
5
0
2
7
0

HINT

样例1的解释

1.对[0 1 3 3 7 0]进行一次第一种操作(复制),我们得到 [0 1 3 3 7 0],[0 1 3 3 7 0]

2.对 [0 1 3 3 7 0],[0 1 3 3 7 0]进行两次第二种操作(交换),将第二个数组中的0与第一个数组中的非0元素交换,我们得到[0 0 0 3 7 0],[1 1 3 3 7 3]

3.对[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]

4.对[0 0 0 3 7 0],[0 0 0 3 7 0],[1 1 3 3 7 3]进行两次第二种操作(交换),将第一个数组中的非0元素与第二个数组中的0元素进行交换,得到[0 0 0 0 0 0],[3 7 0 3 7 0],[1 1 3 3 7 3]

至此,第一个数组中的所有元素都是0,我们共进行了1+2+1+2=6次操作。

样例2的解释

1.对[4 3 2 1]进行一次第一种操作(复制),得到[4 3 2 1],[4 3 2 1]

2.对[4 3 2 1],[4 3 2 1]进行一次第二种操作(交换),将第二个数组里的4与第一个数组里的非4元素进行交换,得到[4 4 2 1],[3 3 2 1]

3.对[4 4 2 1],[3 3 2 1]中的第一个数组进行一次第一种操作(复制),得到[4 4 2 1],[4 4 2 1],[3 3 2 1]

4.对[4 4 2 1],[4 4 2 1],[3 3 2 1]的前两个数组进行两次第二种操作(交换),将第二个数组里的4与第一个数组里的非4元素进行交换,得到[4 4 4 4],[2 1 2 1],[3 3 2 1]

至此,第一个数组中所有的元素都是4,我们共进行了1+1+1+2=5次操作。