#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 2137
#endif

const int INF = 1e9;

struct lct {
  int n;
  vector<pair<int, int>> tree;
  vector<vector<int>>& c;

  lct(int _n, vector<vector<int>>& _c) : c(_c) {
    n = 1;
    while (n < _n) {
      n *= 2;
    }
    tree.resize(2 * n);
  }

  int f(pair<int, int> ff, int x) {
    x = min(x, (int)c[0].size());
    return ff.first + (x <= ff.second + 1 ? 0 : c[ff.second + 1][x - 1]);
  }

  void add(int u, int ul, int ur, pair<int, int> ff) {
    int mid = (ul + ur) / 2;
    bool l = f(ff, ul) < f(tree[u], ul);
    bool m = f(ff, mid) < f(tree[u], mid);
    if (m) {
      swap(tree[u], ff);
    }
    if (ul == ur) {
      return;
    }
    if (l != m) {
      add(2 * u, ul, mid, ff);
    } else {
      add(2 * u + 1, mid + 1, ur, ff);
    }
  }

  int get(int x) {
    int res = INF;
    int u = x + n;
    while (u > 0) {
      res = min(res, f(tree[u], x));
      u /= 2;
    }
    return res;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int inv = 0;
    vector<vector<int>> e(n);
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (a[j] < a[i]) {
          ++inv;
          e[i + 1].push_back(inv);
          e[j].push_back(-inv);
        }
      }
    }
    vector<vector<int>> c(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
      set<int> s;
      int cnt = 0;
      for (int j = i; j < n; j++) {
        for (int x : e[j]) {
          if (x > 0) {
            s.insert(x);
          } else if (x < 0 && s.count(-x)) {
            s.erase(-x);
            cnt++;
          }
        }
        c[i][j] = cnt;
      }
    }
    vector<lct> dp(k + 1, lct(n + 1, c));
    for (int i = 1; i < n; i++) {
      for (int j = k - 1; j >= 0; j--) {
        dp[j + 1].add(1, 0, dp[j + 1].n - 1, {dp[j].get(i), i});
      }
    }
    int ans = INF;
    for (int i = 0; i <= k; i++) {
      ans = min(ans, dp[i].get(n));
    }
    cout << ans << '\n';
  }
}