A. Make All Equal

time limit per test

1 second

memory limit per test

256 megabytes

You are given a cyclic array a1,a2,…,ana1,a2,…,an.

You can perform the following operation on aa at most n−1n−1 times:

• Let mm be the current size of aa, you can choose any two adjacent elements where the previous one is no greater than the latter one (In particular, amam and a1a1 are adjacent and amam is the previous one), and delete exactly one of them. In other words, choose an integer ii (1≤i≤m1≤i≤m) where ai≤a(imodm)+1ai≤a(imodm)+1 holds, and delete exactly one of aiai or a(imodm)+1a(imodm)+1 from aa.

Your goal is to find the minimum number of operations needed to make all elements in aa equal.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤5001≤t≤500). The description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤1001≤n≤100) — the length of the array aa.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) — the elements of array aa.

Output

For each test case, output a single line containing an integer: the minimum number of operations needed to make all elements in aa equal.

Example

Input

Copy

7

1

1

3

1 2 3

3

1 2 2

5

5 4 3 2 1

6

1 1 2 2 3 3

8

8 7 6 3 8 7 6 3

6

1 1 4 5 1 4

Output

Copy

0
2
1
4
4
6
3

Note

In the first test case, there is only one element in aa, so we can't do any operation.

In the second test case, we can perform the following operations to make all elements in aa equal:

• choose i=2i=2, delete a3a3, then aa would become [1,2][1,2].
• choose i=1i=1, delete a1a1, then aa would become [2][2].

It can be proven that we can't make all elements in aa equal using fewer than 22 operations, so the answer is 22.

解题说明：水题，统计数列中那个数字出现的次数最多，删除其他数字就是答案。可以用数组来记录每个数字出现的次数，找出最大值再用总次数相减即可。

#include<stdio.h>int main()
{int t;scanf("%d", &t);while (t--){int n, m = 0;scanf("%d", &n);int a[101];for (int i = 0; i < n; i++){a[i] = 0;}for (int i = 0; i < n; i++){int x;scanf("%d", &x);a[x - 1]++;if (a[x - 1] > m){m = a[x - 1];}}printf("%d\n", n - m);}return 0;
}