#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<pair<int,int> ,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define all(x) begin(x),end(x)
const lld INF=1e18;
lld In[6000][6005];
lld arr[6000];
ordered_set O;
lld DP[6000][6005];
void calc(int l, int r, int optl, int optr, int level){
    if(l>r)return;
    int mid=(l+r)/2;
    int best=-1;
    rep(i,optl,min(mid,optr+1)){
        if(DP[mid][level]>DP[i][level-1]+In[i][mid-1]){
            DP[mid][level]=DP[i][level-1]+In[i][mid-1];
            best=i;
        }
    }
    //~ cout<<mid<<" "<<level<<" "<<DP[mid][level]<<" "<<best<<endl;
    calc(l,mid-1,optl,best,level);
    calc(mid+1,r,best,optr,level);
}
void solve(){
	int n,k;
    cin>>n>>k;
    k++;
    rep(i,0,n)cin>>arr[i];
    rep(i,0,n){
        O.clear();
        lld inv=0;
        rep(j,i,n){
            inv+=O.size()-O.order_of_key(pair<int,int>(arr[j],j));
            O.insert(pair<int,int>(arr[j],j));
            In[i][j]=inv;
            //cout<<i<<" "<<j<<" "<<inv<<endl;
        }
    }
    
    rep(i,0,n+1){
        rep(j,0,k+1)DP[i][j]=INF;
    }
    DP[0][0]=0;
    rep(j,1,k+1)calc(j,n,j-1,n,j);
    //~ rep(i,0,k+1){
        //~ rep(j,0,n+1)cout<<DP[j][i]<<" ";
        //~ cout<<endl;
    //~ }
    cout<<DP[n][k]<<"\n";
    
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--){
		solve();
	}
}