给定一个循环数组 a1,a2,…,ana1​,a2​,…,an​。

你可以对 aa 至多执行 n−1n−1 次以下操作：

• 设 mm 为 aa 的当前大小，你可以选择任何两个相邻的元素，其中前一个不大于后一个（特别地，amam​ 和 a1a1​ 是相邻的，amam​ 是前一个），并删除其中的一个。换句话说，选择一个整数 ii (1≤i≤m1≤i≤m) 使得 ai≤a(imodm)+1ai​≤a(imodm)+1​ 成立，然后从 aa 中删除 aiai​ 或 a(imodm)+1a(imodm)+1​ 之一。

你的目标是找到使得 aa 中所有元素相等所需的最小操作次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 tt (1≤t≤5001≤t≤500)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 nn (1≤n≤1001≤n≤100) — 数组 aa 的长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana1​,a2​,…,an​ (1≤ai≤n1≤ai​≤n) — 数组 aa 的元素。

输出

对于每个测试用例，输出一行包含一个整数：使得 aa 中所有元素相等所需的最小操作次数。

示例

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

0
2
1
4
4
6
3

注意

在第一个测试用例中，aa 中只有一个元素，因此我们无法进行任何操作。

在第二个测试用例中，我们可以执行以下操作使得 aa 中所有元素相等：

• 选择 i=2i=2，删除 a3a3​，然后 aa 将变为 [1,2][1,2]。
• 选择 i=1i=1，删除 a1a1​，然后 aa 将变为 [2][2]。

可以证明，我们无法使用少于 22 次操作使得 aa 中所有元素相等，因此答案是 22。

//找规律，总数减去最多相等数的个数
#include<bits/stdc++.h>
using namespace std;
map<int,int>mapp;
int main(){int t;cin>>t;while(t--){mapp.clear();int n,maxn=-1;cin>>n;int h=n;while(h--){int k;cin>>k;mapp[k]++;maxn=max(mapp[k],maxn);}cout<<n-maxn<<endl;}
}