#include<iostream>
#include<map>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int inf=1e9+7,N=6005;
int n,m;
int tot,a[N],b[N],f[N][N];
#define lowbit(x) x&-x
class Tree_Array {
	private:
		int bit[N];
	public:
		void assign(Tree_Array &t) {
			for(int i=1; i<=n; i++)
				bit[i]=t.bit[i];
		}
		void clear() {
			for(int i=0; i<=n; i++)
				bit[i]=0;
		}
		void add_mx(int x,int t) {
			while(x)bit[x]=max(bit[x],t),x-=lowbit(x);
		}
		int get_mx(int x) {
			int ans=0;
			while(x<=n)ans=max(bit[x],ans),x+=lowbit(x);
			return ans;
		}
		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 prepare() {
	scanf("%d%d",&n,&m);
	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]];
}
void Get_f() {
	for(int d=1; d<=n; d++) {
		set<int> S;
		set<int> :: iterator itr;
		S.insert(1);
		int sum=0,layer=0;
		itr=S.begin();
		for(int i=d; 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=d; 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);
			sum=sum-bit2[layer].get(tot-a[i]);
			f[d+1][i]=sum;//[d+1,i]
			bit2[layer].add(tot-a[i]+1,1);
		}
		layer=0,itr=S.begin();
		for(int i=d; i<=n; i++) {
			if(itr!=S.end()&&i==*itr) {
				layer++,itr++;
			}
			bit2[layer].add(tot-a[i]+1,-1);
		}
	}
}
struct node {
	int now,sum,cnt;
} ;
void Get_ans() {
	queue <node> Q;
	for(int i=1; i<=n-m+1; i++)Q.push(node{i,0,0});
	printf("[%d]\n",f[4][6]);
	int ans=inf;
	bit1[0].clear();
	while(!Q.empty()) {
		int x=Q.front().now,res=Q.front().sum,c=Q.front().cnt;
		Q.pop();
		if(c==m) {
			if(x==n+1)ans=min(ans,res);
			continue;
		}
		if(bit1[0].get_mx(x+1)>res)continue;
		bit2[0].add_mx(x,res);
		for(int i=x; i<=n; i++) {
			Q.push(node{i+1,res+f[x][i],c+1});
		}
		bit1[0].assign(bit2[0]);
		bit2[0].clear();
	}
	printf("%d\n",ans);
}
void solve() {
	prepare();
	Get_f();
	Get_ans();
}
int main() {
	//freopen("data.in","r",stdin);
	//freopen("my.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--) solve();
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}