#include<bits/stdc++.h>

//#pragma GCC optimize ("Ofast")

using namespace std;

#define rep(i,a,b) for(ll i = a; i<b;i++)
#define rrep(i,a,b) for(ll i = b-1; i>=a;i--)
#define trav(x,a) for(auto &x: a)
#define all(v) v.begin(),v.end()
#define sz(v) ll(v.size())

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;

struct FT {
	vector<ll> s;
	FT(int n) : s(n) {}
	void update(int pos, ll dif) { // a[pos] += dif
		for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
	}
	ll query(int pos) { // sum of values in [0, pos)
		ll res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
};

void solve(){
    ll n,k;
    cin>>n>>k;

    vl a(n);
    rep(i,0,n) cin>>a[i];
    vl as = a;
    sort(all(as));
    map<ll,ll> comp;
    rep(i,0,n) comp[as[i]] = i;
    rep(i,0,n) a[i] = comp[a[i]];
    reverse(all(a));

    vector<vl> invs(n,vl(n+1));
    rep(i,0,n){
        FT ft(n);
        rep(j,i+1,n+1){
            invs[i][j] = invs[i][j-1] + ft.query(a[j-1]); 
            ft.update(a[j-1],1);   

            // cout<<"invs["<<i<<"]["<<j<<"]="<<invs[i][j]<<endl;
        
        }
    }


    vector<vl> dp(k+2,vl(n+1,1e18));
    dp[0][n] = 0;
    rep(ki,1,k+2){
        ll optNext = n;

        for(ll i = n-1;i>=0;i--){
            auto f = [&](ll j){
                return dp[ki-1][j]+invs[i][j];
            };
            while(optNext>i+1 && f(optNext-1)<=f(optNext)) optNext--;
            dp[ki][i] = f(optNext);

            // cout<<"dp["<<ki<<"]["<<i<<"]="<<dp[ki][i]<<", optNext="<<optNext<<endl;
        }
    }

    cout<<dp[k+1][0]<<"\n";
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    ll t; cin>>t;
    while(t--) solve();
}