#include <bits/stdc++.h>

using namespace std;

const int N = 6010;

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

struct BIT {
  int tr[N];
  
  void modify(int u, int x) {
    for (int i = u; i <= 6000; i += i & -i) tr[i] += x;
  }
  
  int query(int u) {
    if (u < 0) return 0;
    int res = 0;
    for (int i = u; i; i -= i & -i) res += tr[i];
    return res;
  }
  
  void clear() {
    memset(tr, 0, sizeof tr);
  }
}T;

int f[N][N];

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

int solve() {
  cin >> n >> k;
  
  for (int i = 1; i <= n; ++ i ) cin >> a[i];
  
  for (int l = 1; l <= n; ++ l ) {
    T.clear();
    for (int r = l; r <= n; ++ r ) {
      w[l][r] = w[l][r - 1] + T.query(6000) - T.query(a[r]);
      T.modify(a[r], 1);
    }
  }
  
  memset(f, 0x3f, sizeof f);
  f[0][0] = 0;
  // for (int i = 0; i <= n; ++ i )
    // for (int j = 0; j <= n; ++ j )
      // f[i][j] = 
  for (int i = 1; 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;
}