#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// #define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
struct segTree {
    int base;
    vi t;
    segTree(int n) {
        base = (1 << (31 - __builtin_clz(n) + 1));
        t.assign(2 * base, 0);
    }
    void add(int idx, int val) {
        int cur = base + idx;
        while(cur > 0) {
            t[cur] += val;
            cur /= 2;
        }
    }
    int query(int l, int r) {
        int a = base + l - 1, b = base + r + 1, ans = 0;
        while(a / 2 != b / 2) {
            if(a % 2 == 0) ans += t[a + 1];
            if(b % 2 == 1) ans += t[b - 1];
            a /= 2, b /= 2;
        }
        return ans;
    }
};
const int INF = 1e7;
int n;
vector<vector<int>> dp;
vector<vector<int>> cost;
void rec(int l, int r, int k, int optl, int optr) {
    if(r < l) return;

    int mid = l + (r - l) / 2, opt = -1;
    for(int j = optl; j <= min(optr, mid - 1); j++) {
        int cur = dp[j][k - 1] + cost[j][mid - 1];
        if(dp[mid][k] >= cur) {
            dp[mid][k] = cur, opt = j;
        }
    }
    rec(l, mid - 1, k, optl, opt);
    rec(mid + 1, r, k, opt, optr);
}
void test_case() {
    int k;
    cin >> n >> k;
    dp.assign(n + 1, vector<int>(k + 1, INF));
    cost.assign(n + 1, vector<int>(n + 1, 0));
    vector<int> v(n + 1, 0);
    for(int i = 1; i <= n; i++) cin >> v[i];
    vi d = v;
    sort(all(d));
    d.resize(unique(all(d)) - d.begin());
    for(int i = 0; i <= n; i++) {
        v[i] = lower_bound(all(d), v[i]) - d.begin();
    }

    for(int i = 0; i <= n; i++) {
        segTree t(n + 1);
        for(int j = i; j <= n; j++) {
            cost[i][j] = (j == 0 ? 0 : cost[i][j - 1]) + t.query(v[j] + 1, t.base - 1);
            t.add(v[j], 1);
        }
    }
    dp[0][0] = 0;
    for(int j = 1; j <= k; j++) {
        rec(1, n, j, 0, n);
    }
    int ans = INF;
    for(int i = 1; i <= n; i++) {
        ans = min(ans, dp[i][k] + cost[i][n]);
    }
    cout << ans << "\n";
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc = 1;
    cin >> tc;
    while(tc--) {
        test_case();
    }
    return 0;
}