#ifdef MY_LOCAL
#include "D://competitive_programming/debug/debug.h"
#define debug(x) cerr << "[" << #x<< "]:"<<x<<"\n"
#else
#define debug(x) 
#endif
#define REP(i, n) for(int i = 0; i < (n); i ++)
#define REPL(i,m, n) for(int i = (m); i < (n); i ++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define sz(X) ((int)X.size())
#define READ(arr) for(auto &a: arr){cin>>a;}
#define SUM(arr) accumulate((arr).begin(), (arr).end(), 0LL)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef tree<ii,null_type,less<ii>, rb_tree_tag, tree_order_statistics_node_update> ost;
const ll INF = 1e18;
void dnCdp(int L, int R, int optL, int optR, vi &oridp, vi &ndp, vvi &vals) {
	if (L > R) return;
	assert(optL <= optR);
	int mid = (L + R)/2;
	ii bst = {INF, INF};
	//debug(mid);
	//debug(optL);
	//debug(optR);
	REPL(opt, optL, min(optR, mid)+1) {
		int ans = oridp[opt] + (opt + 1 > mid ? 0 : vals[opt+1][mid]);
		bst = min(bst, {ans, opt});
	}
	//debug(bst);debug(mid);
	auto [val, which] = bst;
	ndp[mid] = val;
	assert(which <= mid);
	dnCdp(L, mid -1, optL, which, oridp, ndp, vals);
	dnCdp(mid+1,R, which, optR, oridp, ndp, vals);
}
int solve() {
	int n,k;cin>>n>>k;
	vi arr(n);
	READ(arr);
	vvi val(n, vi(n,0));
	REP(i, n) {
		int tot = 0;
		ost tr;
		REPL(j, i, n) {
			int x = arr[j];
			int gg = sz(tr) - tr.order_of_key({x, INF});
			tot += gg;
			val[i][j] = tot;
			tr.insert({x, j});
		}
	}
	//debug(val);
	vi dp(n);
	REP(i, n) {
		dp[i] = val[0][i];
	}
	REP(iter, k) {
		vi ndp(n);
		//debug(dp);
		dnCdp(0, n-1, 0, n-1, dp, ndp, val);
		//debug(ndp);
		swap(ndp, dp);
	}
	return dp[n-1];

}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin>>tc;
	REP(i, tc) {
		cout<<solve()<<"\n";
	}

}