#include <bits/stdc++.h>

#define maxn 6005

using namespace std;

int n, k;
int a[maxn];
int b[maxn];
int f[maxn][maxn];

int t1[maxn];
int t2[maxn];

void add(int t[], int x, int k) {
	for (; x <= n; x += x & -x) t[x] += k;
}

int qry(int t[], int l, int r) {
	int res = 0;
	for (int x = l - 1; x; x -= x & -x) res -= t[x];
	for (int x = r; x; x -= x & -x) res += t[x];
	return res;
}

int vl;
int pl, pr;

void moveto(int ql, int qr) {
	while (pl > ql) {
		--pl;
		add(t1, a[pl], 1);
		vl += qry(t2, 1, a[pl] - 1);
	}
	while (pr < qr) {
		add(t2, a[pr], -1);
		vl -= qry(t1, a[pr] + 1, n);
		add(t1, a[pr], 1);
		vl += qry(t2, 1, a[pr] - 1);
		++pr;
	}
	while (pl < ql) {
		add(t1, a[pl], -1);
		vl -= qry(t2, 1, a[pl] - 1);
		++pl;
	}
	while (pr > qr) {
		--pr;
		add(t1, a[pr], -1);
		vl -= qry(t2, 1, a[pr] - 1);
		add(t2, a[pr], 1);
		vl += qry(t1, a[pr] + 1, n);
	}
//	assert(vl >= 0 && pl <= pr);
} 

void solve(int d, int l, int r, int L, int R) {
	if (r < l) return;
	if (L == R) {
		for (int i = l; i <= r; i++) moveto(i, L), f[d][i] = f[d - 1][L];
		return;
	}
//	cout<<d<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
	int mid = (l + r) >> 1;
	int ql = max(L, mid + 1);
	int qr = R;
	int res = -1, id = 0;
	for (int i = ql; i <= qr; i++) {
		moveto(mid, i);
		if (res < f[d - 1][i] + vl) {
			res = f[d - 1][i] + vl;
			id = i;
		}
	}
//	assert()
	f[d][mid] = res;
//	cout<<mid<<" "<<res<<" "<<id<<endl;
	solve(d, mid + 1, r, id, R);
	solve(d, l, mid - 1, L, id);
}

int main() {
//	freopen("dt.in", "r", stdin);
	int T;
	scanf("%d", &T);
//	int T = 1;
	while (T--) {
		memset(t1, 0, sizeof t1);
		memset(t2, 0, sizeof t2);
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
		if (k >= n - 1) {
			puts("0");
			continue;
		}
		sort(b + 1, b + n + 1);
		int tot = unique(b + 1, b + n + 1) - b - 1;
		for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
		int ans = 0;
		pl = pr = n + 1;
		vl = 0;
		for (int i = 1; i <= k; i++) {
			solve(i, 1, n, 1, n);
			ans = max(ans, f[i][1]);
			if (f[i][1] == f[i - 1][1]) break;
		}
//		printf("%d\n", ans);
		memset(t1, 0, sizeof t1);
		for (int i = 1; i <= n; i++) {
			ans -= qry(t1, a[i] + 1, n);
			add(t1, a[i], 1);
		}
		printf("%d\n", -ans);
	}
	return 0;
}
/*
2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1
*/