#include <bits/stdc++.h>
#define pb emplace_back

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

using namespace std;

const int maxn = 6005;

using LDB = long double;
using DB = double;
using LL = long long;

int inv[maxn][maxn];

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> F(n + 5 , n * n), G(n + 5, n * n), A(n + 5, 0);
	for(int i = 1; i <= n; ++i){
		cin >> A[i];
	}

	reverse(A.begin() + 1, A.begin() + n + 1);
	for(int i = 1; i <= n; ++i)
		for(int j = i; j <= n; ++j)
			inv[i][j] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = i; j >= 1; --j){
			if(A[j] < A[i]){
				++inv[j][i];
			}
			inv[j][i] += inv[j + 1][i];
		}
	}
	
	for(int j = 1; j <= n; ++j){
		for(int i = j; i <= n; ++i){
			inv[j][i] += inv[j][i - 1];
		}
	}

	// {
	// 	cerr << "A\n";
	// 	for(int i = 1; i <= n; ++i)
	// 		cerr << A[i] << " ";
	// 	cerr << '\n';
	// }
	// {
	// 	for(int i = 1; i <= n; ++i)
	// 		for(int j = i; j <= n; ++j)
	// 			cerr << i << " " << j << " " << inv[i][j] << '\n';
	// }

	function<void(int, int, int, int)> dp = [&](int l, int r, int tl, int tr) -> void{
		if(l > r)
			return;
		int mid = (l + r) >> 1;
		int best = 0;
		F[mid] = n * n;
		for(int i = tl; i <= mid; ++i){
			int t = inv[i][mid] + G[i - 1];
			if(t < F[mid]){
				best = i;
				F[mid] = t;
			}
		}
		if(l == r)
			return;
		
		dp(l, mid - 1, tl, best); dp(mid + 1, r, best, tr);
	};

	for(int i = 0; i <= n; ++i)
		F[i] = (i == 0 ? 0 : n * n);
	for(int i = 1; i <= m; ++i){
		G = F;
		dp(1, n, 1, n);

		// {
		// 	cerr << "round : " << i << '\n';
		// 	for(int j = 1; j <= n; ++j)
		// 		cerr << F[j] << " ";
		// 	cerr << '\n';
		// }
	}

	int ans = n * n;
	for(int i = 0; i <= n; ++i){
		ans = min(ans, F[i] + inv[i + 1][n]);
	}
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T;
	scanf("%d", &T);
	while(T--){
		solve();
	}
	return 0;
}