// qdd on Feb 12, 2023
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define ALL(x) begin(x), end(x)

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v) is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool f = 0;
  for (const T& x : v) (f ? os << ' ' : os) << x, f = 1;
  return os;
}

// repeating elements with same id
template <class T>
vector<int> unique_dc(const vector<T>& a, int start_id) {
  int n = a.size();
  vector<T> t(a);
  sort(t.begin(), t.end());
  t.resize(unique(t.begin(), t.end()) - t.begin());
  vector<int> id(n);
  for (int i = 0; i < n; i++) {
    id[i] = start_id + lower_bound(t.begin(), t.end(), a[i]) - t.begin();
  }
  return id;
}

struct fenwick {
  int n;
  vector<int> t;
  fenwick(int n) : n(n), t(n + 1) {}
  void add(int p, int x) {
    for (; p <= n; p += p & -p) t[p] += x;
  }
  int get(int p) {
    int a = 0;
    for (; p > 0; p -= p & -p) a += t[p];
    return a;
  }
};

int inv[6001][6001];

void sol() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  cin >> a;
  a = unique_dc(a, 1);
  int mx = *max_element(ALL(a));
  // inv[i][j] => invs in [i, j]
  for (int i = 0; i < n; i++) {
    fenwick t(mx);
    int now = 0;
    for (int j = i; j < n; j++) {
      now += t.get(mx) - t.get(a[j]);
      t.add(a[i], 1);
      inv[i][j] = now;
    }
  }
  vector<ll> dp_before(n), dp_cur(n);
  // compute dp_cur[l], ... dp_cur[r] (inclusive)
  function<void(int, int, int, int)> compute = [&](int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    pair<ll, int> best = {LLONG_MAX, -1};
    for (int j = optl; j <= min(mid, optr); j++) {
        best = min(best, {(j ? dp_before[j - 1] : 0) + inv[j][mid], j});
    }
    dp_cur[mid] = best.first;
    int opt = best.second;
    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
  };
  for (int i = 0; i < n; i++) {
    dp_before[i] = inv[0][i];
  }
  for (int i = 1; i <= k; i++) {
    compute(0, n - 1, 0, n - 1);
    dp_before = dp_cur;
  }
  cout << dp_before[n - 1] << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    sol();
  }
  return 0;
}