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

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

struct segtree {
  struct node {
    int val = 0;
    int add = 0;
  };

  int n;
  vector<node> tree;

  segtree(int _n = 0) {
    n = 1;
    while (n < _n) {
      n *= 2;
    }
    tree.resize(2 * n);
  }

  node join(const node& a, const node& b) {
    node res;
    res.val = max(a.val, b.val);
    return res;
  }

  void push(int u, int) {
    for (int v : {2 * u, 2 * u + 1}) {
      tree[v].val += tree[u].add;
      tree[v].add += tree[u].add;
    }
    tree[u].add = 0;
  }

  template<typename F>
  void run(int u, int ul, int ur, int l, int r, bool mod, F&& f) {
    if (ul >= l && ur <= r) {
      f(u, ur - ul + 1);
      return;
    }
    if (ul > r || ur < l) {
      return;
    }
    push(u, ur - ul + 1);
    int mid = (ul + ur) / 2;
    run(2 * u, ul, mid, l, r, mod, f);
    run(2 * u + 1, mid + 1, ur, l, r, mod, f);
    if (mod) {
      tree[u] = join(tree[2 * u], tree[2 * u + 1]);
    }
  }

  node get(int l, int r) {
    node res;
    run(1, 0, n - 1, l, r, false, [&] (int u, int) {
      res = join(res, tree[u]);
    });
    return res;
  }

  void modify(int l, int r, int a) {
    run(1, 0, n - 1, l, r, true, [&] (int u, int) {
      tree[u].val += a;
      tree[u].add += a;
    });
  }

  void modify(int i, int a) {
    run(1, 0, n - 1, i, i, true, [&] (int u, int) {
      tree[u].val = max(tree[u].val, a);
    });
  }
};

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];
    }
    vector<vector<pair<int, int>>> s(n);
    vector<int> p(n);
    int inv = 0;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (a[j] < a[i]) {
          inv++;
          s[j].push_back({i + 1, 1});
        }
      }
    }
    vector<segtree> dp(k + 1, segtree(n));
    for (int i = 0; i < n; i++) {
      for (int j = k - 1; j >= 0; j--) {
        dp[j + 1].modify(i, dp[j].get(0, i - 1).val);
      }
      for (auto [l, w] : s[i]) {
        for (int j = 1; j <= k; j++) {
          dp[j].modify(l, i, w);
        }
      }
    }
    debug(inv);
    int ans = 0;
    for (int i = 0; i <= k; i++) {
      ans = max(ans, dp[i].get(0, n - 1).val);
    }
    cout << inv - ans << '\n';
  }
}