#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long i64;
const int N=2e5+5;
int t;
int n;
int a[N];
int c1[N],c2[N];
int id[N];
bool cmp(int x,int y)
{
	return c2[x]>c2[y];
}
void skr(void)
{
	cin>>n;
	for(int i=1;i<=n+1;i++)
	{
		c1[i]=c2[i]=0;
		id[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i%2==1)
		{
			c1[a[i]]++;
		}
		else
		{
			c2[a[i]]++;
		}
	}
	sort(id+1,id+n+1,cmp);
	map<pair<int,int>,int> mp;
	for(int l=1,r;l<n;l=r)
	{
		r=l+1;
		int x=a[l],y=a[r];
		if(l%2==0)
		{
			swap(x,y);
		}
		while(r<n)
		{
			if((r+1)%2==1&&a[r+1]!=x)
			{
				break;
			}
			if((r+1)%2==0&&a[r+1]!=y)
			{
				break;
			}
			r++;
		}
		mp[{x,y}]+=r-l+1>>1;
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		int x=a[i],y=a[i+1];
		if(i%2==0)
		{
			swap(x,y);
		}
		ans=max(ans,c1[y]+c2[x]-mp[{x,y}]);
	}
	for(int i=1;i<=n+1;i++)
	{
		int t=1;
		while(mp[{id[i],i}]||i==id[t])
		{
			t++;
		}
		ans=max(ans,c1[i]+c2[id[t]]);
	}
	printf("%d\n",&n-ans);
}
int main(void)
{
	scanf("%d",&t);
	while(t--)
	{
		skr();
	}
	return 0;
}