#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
const ll INF = 2e18;

const int maxn = 6010;
const int inf = 1000000010;

int n, k;

int v[maxn];
int dp[2][maxn];
int sv[maxn][maxn];

int numInversions(int l, int r)
{
    int ans = sv[r][r] + sv[l - 1][l - 1];
    ans -= sv[r][l - 1] + sv[l - 1][r];

    return ans;
}

void divAndConquer(int line, int l, int r, int optmin, int optmax)
{
    if( l > r )
        return;

    int mid = (l + r)/2;
    int optmid = mid, optValue = dp[line^1][mid - 1];

    for(int i = optmin ; i <= optmax && i <= mid ; i++)
    {
        int curValue = dp[line^1][i - 1] + numInversions( i , mid );

        if( curValue < optValue )
            optValue = curValue, optmid = i;
    }

    dp[line][mid] = optValue;

    divAndConquer( line , l , mid - 1 , optmin , optmid );
    divAndConquer( line , mid + 1 , r , optmid , optmax );
}

void solve()
{
    cin >> n >> k;
    k++;

    for(int i = 1 ; i <= n ; i++)
        cin >> v[i];

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            sv[i][j] = sv[i - 1][j] + sv[i][j - 1] - sv[i - 1][j - 1] + (v[i] > v[j] && i < j);

    for(int i = 0 ; i <= n ; i++)
        dp[1][i] = sv[i][i];

    for(int line = 2 ; line <= k ; line++)
        divAndConquer( line&1 , 1 , n , 1 , n );

    cout << dp[k%2][n] << "\n";
}

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

    int t;
    cin >> t;

    while( t-- )
        solve();

    return 0;
}