#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t,n,k,a[6011],sum[6011][6011];pair<ll,int> dp[6011];
int main()
{
	scanf("%d",&t);while(t--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;++i)scanf("%d",a+i);int cnt=0;
		for(int i=0;i<=n+1;++i)for(int j=i;j<=n+1;++j)sum[i][j]=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=i+1;j<=n;++j)if(a[i]>a[j])++sum[i][j],++cnt;
		}
		if(!k){printf("%d\n",cnt);continue;}
		for(int i=n;i;--i)
		{
			for(int l=1;l+i-1<=n;++l)
			{
				int r=l+i-1;
				sum[l][r]+=sum[l-1][r]+sum[l][r+1]-sum[l-1][r+1];
			}
		}
		int L=0,R=n*n,K=0;ll ans=0;
		while(L<=R)
		{
			int M=L+R>>1;
			dp[1]=pair<ll,int>(0,0);
			for(int i=2;i<=n;++i)
			{
				dp[i].first=-1e18;
				for(int j=1;j<i;++j)
				{
					int w=sum[i-1][i]-sum[j-1][i];
					dp[i]=max(dp[i],pair<ll,int>(dp[j].first+w-M,dp[j].second+1));
				}
			}
			auto res=dp[1];
			for(int i=2;i<=n;++i)res=max(res,dp[i]);
			if(res.second>=k)K=M,ans=res.first,L=M+1;else R=M-1;
		}
		printf("%lld\n",cnt-(ans+1ll*k*K));
	}return 0;
}