#include <bits/stdc++.h>

#define maxn 6005
#define ll long long

using namespace std;

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

ll f[maxn];
int g[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);
	}
//	cout<<pl<<" "<<pr<<" "<<vl<<endl;
//	assert(vl >= 0 && pl <= pr);
}

pair<ll, int> check(ll x) {
	f[n] = 0;
	for (int i = n - 1; i; i--) {
		f[i] = -1e18;
		for (int j = i + 1; j <= n; j++) {
			moveto(i, j);
			if (f[i] < f[j] + vl - x) {
				f[i] = f[j] + vl - x;
				g[i] = g[j] + 1;
			}
		}
	}
//	cout<<x<<" "<<f[1]<<" "<<g[1]<<endl;
	return {f[1], g[1]};
}

int main() {
//	freopen("dt.in", "r", stdin);
//	freopen("dt.out", "w", stdout);
	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;
		pl = pr = n + 1;
		vl = 0;
		ll l = 0, r = 1e18, mid;
		while (l < r) {
			mid = (l + r) >> 1;
			if (check(mid).second <= k) r = mid;
			else l = mid + 1;
		}
		auto res = check(l);
//		cout<<l<<" "<<res.first<<" "<<res.second<<endl;
		ll ans = res.first + l * res.second;
//		printf("%lld\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("%lld\n", -ans);
	}
	return 0;
}
/*
2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1
*/