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

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;

typedef tree<
pair<ll,ll>,
null_type,
greater<pair<ll,ll>>,
rb_tree_tag,
tree_order_statistics_node_update>
rankset;

ll N, K;

vector<ll> A;

vector<vector<ll>> invs;

pair<ll,ll> best(ll lambda) {
    vector<pair<ll,ll>> dp(N+1);
    dp[0] = {0,0};
    for(ll i = 1; i <= N; i++) {
        dp[i] = dp[i-1];
        dp[i].first += lambda;
        dp[i].second++;
        for(ll j = 0; j <= i-1; j++) {
            dp[i] = min(dp[i], {dp[j].first + invs[j][i-1] + lambda, dp[j].second + 1});
        }
    }
    return dp[N];
}

ll aliens_trick(bool convex, bool gen_eq = 0) {
    ll l = gen_eq ? -4e18/N : -4e18*!convex;
    ll r = gen_eq ? 4e18/N : 4e18*convex;
    int sgn = convex ? 1 : -1;
    while(l < r) {
        ll m = l + (r-l)/2;
        sgn*best(m).second <= sgn*K ? r = m : l = m+1;
    }
    return best(r).first - r*K;
}


void solve() {
     cin >> N; cin >> K; K++; K = min(N,K);
   A = vector<ll>(N);
   for(ll i = 0; i < N; i++) cin >> A[i];

   invs = vector<vector<ll>>(N, vector<ll>(N));


   for(ll i = 0; i < N; i++) {
    rankset r;
    ll iv = 0;
    for(ll j = i; j < N; j++) {
        pair<ll,ll> key = {A[j], (j-i)};
        iv += r.order_of_key(key);
        r.insert(key);
        invs[i][j] = iv;
    }
   }

   cout << aliens_trick(true) << endl;

    
}

int main() {
    ll Z; cin >> Z;
    while(Z--) solve();
}