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

const int maxn = 6010;

int n,K;
int a[maxn];
int pr[maxn][maxn],cost[maxn][maxn];

struct node
{
	ll c;
	int k;
}f[maxn];
void dp(const ll mid)
{
	f[n+1]=(node){0,0};
	for(int i=n;i>=1;i--)
	{
		f[i]=(node){cost[i][n],0};
		for(int j=i;j<n;j++)
		{
			node temp=(node){f[j+1].c+cost[i][j]+mid,f[j+1].k+1};
			if( f[i].c>temp.c || (f[i].c==temp.c&&f[i].k<temp.k) )
				f[i]=temp;
		}
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>K;
		for(int i=1;i<=n;i++) cin>>a[i];
		
		for(int r=1;r<=n;r++)
		{
			pr[r][r]=0;
			for(int l=r-1;l>=1;l--)
				pr[r][l]=pr[r][l+1]+(a[l]>a[r]);
		}
		for(int l=1;l<=n;l++)
		{
			cost[l][l]=0;
			for(int r=l+1;r<=n;r++)
				cost[l][r]=cost[l][r-1]+pr[r][l];
		}
		
		int inf=(n/2)*(n-n/2);
		ll l=-inf,r=inf;
		while(l<=r)
		{
			ll mid=l+(r-l)/2;
			dp(mid);
			if(f[1].k>=K) l=mid+1;
			else r=mid-1;
		}
		dp(l-1);
		cout<<f[1].c-(l-1)*K<<'\n';
	}
	
	return 0;
}