#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6005;
#define M N

int inv[N][N]; // number of inversions in [l,r]
int n,k,a[N],b[N];

int tr[N];
inline int lowbit(int x){ return x & (-x); }
inline void modify(int x,int v){ for(;x <= n;x += lowbit(x)) tr[x] += v; }
inline int query(int x){ int ret = 0; for(;x;x -= lowbit(x)) ret += tr[x]; return ret; }

void init(){
    for(int i = 1;i <= n;i ++){
        memset(tr,0,sizeof(tr));
        for(int sum = 0,j = i;j <= n;j ++){
            sum += (j - i) - query(a[j]);
            inv[i][j] = sum;
            modify(a[j],1);
        }
    }
}

int f[M][M],id;
void solve(int L,int R,int l,int r){
    if(L>R)return;
    int mid = L+R>>1,p=mid,res = 2e9;
    for(int i=max(mid+1,l);i<=r;i++)
        if(res>f[id-1][i]+inv[mid][i-1])
            res = f[id-1][i]+inv[mid][i-1], p = i;
    f[id][mid] = res;
    // cout<<mid<<' '<<res<<endl;
    solve(L,mid-1,l,p);
    solve(mid+1,R,p,r);
}

signed main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        cin >> n >> k;
        int m = 0;
        for(int i = 1;i <= n;i ++){
            cin >> a[i];
            b[++ m] = a[i];
        }
        sort(b + 1,b + 1 + m);
        m = unique(b + 1,b + 1 + m) - b - 1;
        for(int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1,b + 1 + m,a[i]) - b;
        init();
        for(int i=n;i>=1;i--)f[1][i] = inv[i][n];
        for(int i=2;i<=k+1;i++){
            id = i;
            solve(1,n,1,n);
            // for(int j=1;j<=n;j++)
            //     cout<<f[i][j]<<' ';
            // cout<<endl;
        }
        printf("%d\n",f[k+1][1]);
    }
    return 0;
}