#include<iostream>
#include<map>
#include<algorithm>
#include<set>
using namespace std;
const int inf=1e9+7,N=6005;
int tot,a[N],b[N];
#define lowbit(x) x&-x
class Tree_Array {
	private:
		int bit[N];
	public:
		void add(int x,int y) {
			while(x<=tot)bit[x]+=y,x+=lowbit(x);
		}
		int get(int x) {
			int sum=0;
			while(x)sum+=bit[x],x-=lowbit(x);
			return sum;
		}
} bit1[N],bit2[N];
void solve() {
	int n,K;
	scanf("%d%d",&n,&K);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);b[i]=a[i];
	}
	map<int,int>F;
	tot=0;
	sort(b+1,b+1+n);
	for(int i=1; i<=n; i++)
		if(F[b[i]]==0)F[b[i]]=++tot;
	for(int i=1; i<=n; i++)a[i]=F[a[i]];
	int res=0;
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++)
			if(a[j]<a[i])res++;
	}
	set<int> S;
	set<int> :: iterator itr;
	S.insert(1);
	while(K--) {
		int sum=0,mxt=0,k=0,layer=0;
		itr=S.begin();
		for(int i=1; i<=n; i++) {
			if(itr!=S.end()&&i==*itr) {
				layer++,itr++;
			}
			bit1[layer].add(a[i],1);
		}
		layer=0,itr=S.begin();
		for(int i=1; i<=n; i++) {
			if(itr!=S.end()&&i==*itr) {
				layer++,itr++;
			}
			bit1[layer].add(a[i],-1);
			sum=sum+bit1[layer].get(a[i]-1);
//			printf("sum=%d\n",sum);
			sum=sum-bit2[layer].get(tot-a[i]);
			bit2[layer].add(tot-a[i]+1,1);
			if(sum>mxt)mxt=sum,k=i+1;
//			printf(" sum=%d\n",sum);
		}
		layer=0,itr=S.begin();
		for(int i=1; i<=n; i++) {
			if(itr!=S.end()&&i==*itr) {
				layer++,itr++;
			}
			bit2[layer].add(tot-a[i]+1,-1);
		}
//		printf("k=%d\n",k);
		res-=mxt;S.insert(k);
	}
	printf("%d\n",res);
}
int main() {
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}