#include <bits/stdc++.h>

using namespace std;

const int N = 6010;
typedef long long ll;

int n, k, a[N];
ll w[N][N];    // [l, r] 内的逆序对数
ll f[N][N];

void solve(int k, int l, int r, int ql, int qr) {
  // cout << l << ' ' << r << '\n';
  if (l > r) return;
  int mid = l + r >> 1;
  int M = -1;
  for (int i = ql; i <= qr && i < mid; ++ i )
    if (M == -1 || f[k][mid] > f[k - 1][i] + w[i + 1][mid]) {
      f[k][mid] = f[k - 1][i] + w[i + 1][mid];
      M = i;
    }
  // cout << M << '\n';
  solve(k, l, mid - 1, ql, M);
  solve(k, mid + 1, r, M, qr);
}

void add(int x_0, int y_0, int x_1, int y_1) {
  ++ w[x_0][y_0];
  -- w[x_0][y_1 + 1];
  -- w[x_1 + 1][y_0];
  ++ w[x_1 + 1][y_1 + 1];
}

int solve() {
  cin >> n >> k;
  k ++ ; 
  
  for (int i = 1; i <= n; ++ i ) cin >> a[i];
  
  for (int i = 0; i <= n; ++ i )
    for (int j = 0; j <= n; ++ j ) {
      w[i][j] = 0;
      f[i][j] = 1e9;
    }
  
  for (int i = 1; i <= n; ++ i )
    for (int j = i + 1; j <= n; ++ j )
      if (a[i] > a[j]) {
        add(1, j, i, n);
      }
  
  for (int i = 1; i <= n; ++ i )
    for (int j = 1; j <= n; ++ j )
      w[i][j] += w[i - 1][j] + w[i][j - 1] - w[i - 1][j - 1];
  
  for (int i = 1; i <= n; ++ i ) f[1][i] = w[1][i];
  for (int i = 2; i <= k; ++ i ) {
    solve(i, 1, n, 0, n - 1);
  }
  
  return f[k][n];
}

int main() {
  int T;
  cin >> T;
  while (T -- ) cout << solve() << '\n';
  return 0;
}