#include<iostream>
#include<map>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int inf=1e9+7,N=6005;
int n,m,R[N];
int tot,a[N],b[N],f[N][N],excel[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 set(int t) {
			for(int i=0; i<=n; i++)
				bit[i]=t;
		}
		void add_mn(int x,int t) {
			while(x)bit[x]=min(bit[x],t),x-=lowbit(x);
		}
		int get_mn(int x) {
			int ans=inf;
			while(x<=n)ans=min(bit[x],ans),x+=lowbit(x);
			return ans;
		}
		void add(int x,int y) {
			while(x)bit[x]+=y,x-=lowbit(x);
		}
		int get(int x) {
			int sum=0;
			while(x<=n)sum+=bit[x],x+=lowbit(x);
			return sum;
		}
} bit1,bit2;
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 L=1; L<=n; L++) {
		bit1.set(0);
		bit1.add(a[L],1);
		for(int R=L+1; R<=n; R++) {
			f[L][R]=f[L][R-1]+bit1.get(a[R]+1);
			bit1.add(a[R],1);
		}
	}
}
int res[N][N];
void Get_ans() {
	bit1.set(inf);
	bit2.set(inf);
	for(int i=0; i<=n+1; i++)
		for(int j=0; j<=n+1; j++)
			res[i][j]=inf;
	res[0][1]=0;
	for(int i=0; i<=n; i++)R[i]=0;
	for(int c=0; c<=m; c++) {
		int t=c+1;R[n+1]=n;
		for(int j=n; j>c; j--) {
			int tmp=R[j];
			for(int k=R[j+1]; k>=tmp; k--) {
				if(res[c][k]+f[k][j]<res[c+1][j+1]) {
					R[j]=k,t=k;
					res[c+1][j+1]=min(res[c+1][j+1],res[c][t]+f[t][j]);
//					printf("res[%d][%d]=%d\n",c+1,j+1,res[c+1][j+1]);
				}
			}
		}
	}
	printf("%d\n",res[m+1][n+1]);
}
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;
}