#include<bits/stdc++.h>
using namespace std;
namespace IN {
    #define MAX_INPUT 25000003
    #define getc()(p1 == p2 && (p2 = (p1 = buf) + inbuf -> sgetn(buf, MAX_INPUT), p1 == p2) ? EOF : * p1++)
    char buf[MAX_INPUT], * p1, * p2;
    template < typename T > inline bool redi(T & x) {
        static std::streambuf * inbuf = cin.rdbuf();
        x = 0;
        register int f = 0, flag = false;
        register char ch = getc();
        while (!std::isdigit(ch)) {
            if (ch == '-') f = 1;
            ch = getc();
        }
        if (std::isdigit(ch)) x = x * 10 + ch - '0', ch = getc(), flag = true;
        while (std::isdigit(ch)) {
            x = x * 10 + ch - 48;
            ch = getc();
        }
        x = f ? -x : x;
        return flag;
    }
    template < typename T, typename...Args > inline bool redi(T & a, Args & ...args) {
        return redi(a) && redi(args...);
    }
    #undef getc
}

namespace OUT {
    template < typename T > inline void put(T x) {
        static std::streambuf * outbuf = cout.rdbuf();
        static char stack[21];
        static int top = 0;
        if (x < 0) {
            outbuf -> sputc('-');
            x = -x;
        }
        if (!x) {
            outbuf -> sputc('0');
            outbuf -> sputc('\n');
            return;
        }
        while (x) {
            stack[++top] = x % 10 + '0';
            x /= 10;
        }
        while (top) {
            outbuf -> sputc(stack[top]);
            --top;
        }
        outbuf -> sputc('\n');
    }
    inline void putc(const char ch) {
        static std::streambuf * outbuf = cout.rdbuf();
        outbuf -> sputc(ch);
    }
    template < typename T > inline void put(const char ch, T x) {
        static std::streambuf * outbuf = cout.rdbuf();
        static char stack[21];
        static int top = 0;
        if (x < 0) {
            outbuf -> sputc('-');
            x = -x;
        }
        if (!x) {
            outbuf -> sputc('0');
            outbuf -> sputc(ch);
            return;
        }
        while (x) {
            stack[++top] = x % 10 + '0';
            x /= 10;
        }
        while (top) {
            outbuf -> sputc(stack[top]);
            --top;
        }
        outbuf -> sputc(ch);
    }
    template < typename T, typename...Args > inline void put(T a, Args...args) {
        put(a);
        put(args...);
    }
    template < typename T, typename...Args > inline void put(const char ch, T a, Args...args) {
        put(ch, a);
        put(ch, args...);
    }
}
using IN::redi;
using OUT::put;
using OUT::putc;
const int N = 6e3 + 10;
int dp[N][N],cnt[N][N],a[N];
void solve(int l,int r,int l1,int r1,int k){
	if(l > r) return;
	int mid = (l+r)>>1,mid1 = l1;
	for(int i = l1; i <= max(r1,mid); i++){
		if(dp[k][mid] > dp[k-1][i]+cnt[i+1][mid]){
			dp[k][mid] = dp[k-1][i]+cnt[i+1][mid];
			mid1 = i;
		}
	}
	solve(l,mid-1,l1,mid1,k);
	solve(mid+1,r,mid1,r1,k);
}
int T,n,k;
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	redi(T);
	while(T--){
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j <= n; j++){
				cnt[i][j] = 0;
			}
		}
		redi(n);
		redi(k);
		k++;
		for(int i = 1; i <= n; i++) redi(a[i]);
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j <= n; j++){
				if(a[i] > a[j])cnt[i][j]++;
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = i+1; j < n; j++){
				cnt[i][j+1] += cnt[i][j];
			}
		}
		for(int i = n; i > 1; i--){
			for(int j = i+1; j <= n; j++){
				cnt[i-1][j] += cnt[i][j];
			}
		}
		for(int i = 1; i <= k; i++){
			for(int j = 1; j <= n; j++){
				dp[i][j] = 1e9;
			}
		}
		for(int i = 1; i <= n; i++) dp[1][i] = cnt[1][i];
		for(int i = 2; i <= k; i++) solve(1,n,1,n,i);
		put(dp[k][n]);
		puts("\n");
	}

	return 0;
}