#include <bits/stdc++.h>
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

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;
}