#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}
typedef long long ll;
const int MAXN = 6010;

ll n, a[MAXN], val[MAXN][MAXN], sum[MAXN][MAXN], k, f[MAXN][MAXN], pos[MAXN][MAXN];


int main(){
	int t = read();
	while(t--){
		n = read(), k = read();
		for(int i = 1; i <= n; i++)
			for(int kp = 1; kp <= k; kp++)
				f[i][kp] = 0x3f3f3f3f3f3f3f3f;
		for(int i = 1; i <= n; i++)
			a[i] = read(), val[i][i] = 0;
		for(int i = 1; i <= n; i++){
			for(int j = i-1; j >= 1; j--){
				val[j][i] = val[j+1][i] + int(a[j] > a[i]);
//				cout << "AAA : " << j << ' ' << i << ' ' << val[j][i] << endl;
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= i; j++){
				sum[j][i] = sum[j][i-1] + val[j][i];
//				cout << "BBB : " << j << ' ' << i << ' ' << sum[j][i] << endl;
			}
		}
		ll ans = 0x3f3f3f3f3f3f3f3f;
		for(int kp = 1; kp <= k; kp++){
			for(int i = 1; i <= n; i++){
				if(kp == 1) f[i][kp] = sum[1][i];
				else {
					for(int j = pos[i-1][kp]; j < i; j++){
						if(f[j][kp-1] + sum[j+1][i] < f[i][kp]){
							f[i][kp] = f[j][kp-1] + sum[j+1][i];
							pos[i][kp] = j;
						}
					}
				}
				ans = min(ans, f[n][kp]);
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}