#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 6e3 + 100;

int T, n, k;
int a[N], sum[N][N], val[N][N];
int f[N][N];

void init () {
	for (int i = 0; i <= n; i ++ ) 
		for (int j = 0; j <= n; j ++ ) 
			sum[i][j] = 0, val[i][j] = 0, f[i][j] = 0x3f3f3f3f;
	f[0][0] = 0;
}

void solve (int l, int r, int jl, int jr, int j) {
	int mid = l + r >> 1, jc = jl;
	for (int i = jl; i <= min(mid - 1, jr); i ++ ) if (f[i][j - 1] + sum[i + 1][mid] < f[jc][j - 1] + sum[jc + 1][mid]) jc = i;
	f[mid][j] = f[jc][j - 1] + sum[jc + 1][mid];
	if (l < mid) solve(l, mid - 1, jl, jc, j);
	if (mid < r) solve(mid + 1, r, jc, jr, j);
}

int main () {
	cin >> T;
	n = 6e3; init(); 
	while (T -- ) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++ ) cin >> a[i];
		for (int i = 1; i <= n; i ++ ) 
			for (int j = i - 1; j >= 1; j -- ) 
				val[j][i] = val[j + 1][i] + (a[i] < a[j]);
		for (int i = 1; i < n; i ++ ) 
			for (int j = i + 1; j <= n; j ++ ) 
				sum[i][j] = sum[i][j - 1] + val[i][j];
		for (int i = 1; i <= n; i ++ ) f[i][1] = sum[1][i];
		for (int i = 2; i <= k + 1; i ++ ) solve(1, n, 0, n, i);
		cout << f[n][k + 1] << '\n';
		init();
	}
	return 0;
}