#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
int n,k;
int a[6010];
int val[6010][6010];
int f[6010],g[6010];
map<int,int> mp;
int idx;
int t[6010];
const int inf = 1e9;
int lowbit(int x){
	return (x&-x);
}
void add(int x,int c){
	while(x<=idx){
		t[x] += c;
		x += lowbit(x);
	}
	return;
}
int query(int x){
	int res = 0;
	while(x){
		res += t[x];
		x -= lowbit(x);
	}
	return res;
}
void fun(int st){
	for (int i=0;i<=idx;i++) t[i] = 0;
	for (int i=st;i<=n;i++){
		val[st][i] = val[st][i-1]+(query(idx)-query(a[i]));
		add(a[i],1);
	}
	return;
}
void solve(int l,int r,int L,int R){
	int mid = (l+r)/2;
	int pos = 0;
	for (int i=L;i<min(R+1,mid);i++){
		if(g[i]+val[i+1][mid]<f[mid]){
			f[mid] = g[i]+val[i+1][mid];
			pos = i;
		}
	}
	//cout << l << " " << r << " " << pos << "\n";
	if(l==r) return;
	solve(l,mid-1,L,pos);
	solve(mid+1,r,pos,R);
	return; 
}

void solve(){
	mp.clear();
	idx = 0;
	cin >> n >> k;
	++k;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		mp[a[i]] = 0;
	}
	for (auto &i : mp) i.second = ++idx;
	for (int i=1;i<=n;i++) a[i] = mp[a[i]];
	for (int i=1;i<=n;i++) fun(i);
	for (int i=1;i<=n;i++) f[i] = inf;
	f[0] = 0;
	for (int i=1;i<=k;i++){
		for (int j=0;j<=n;j++){
			g[j] = f[j];
			f[j] = inf;
		}
		solve(0,n,0,n);
	}
	cout << f[n] << "\n";
	return;
}

signed main()
{
	int t;
	cin >> t;
	while(t--) solve();
	return 0;
}