#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x;
cin>>x;
return x;
}
const int N = 6e3 + 10;
int dp[N][N],cnt[N][N],a[N];
void solve(int l,int r,int l1,int r1,int k){
if(l > r) return;
int mid = (l+r)>>1,mid1 = l1;
for(int i = l1; i <= ri && i <= mid; i++){
if(dp[k][mid] > dp[k-1][i]+cnt[i+1][mid]){
dp[k][mid] = dp[k-1][i]+cnt[i+1][mid];
mid1 = i;
}
}
solve(l,mid-1,l1,mid1,k);
solve(mid+1,r,mid1,r1,k);
}
int T,n,k;
signed main(){
T = read();
while(T--){
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
cnt[i][j] = 0;
}
}
n = read();
k = read()+1;
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
if(a[i] > a[j])cnt[i][j]++;
}
}
for(int i = 1; i <= n; i++){
for(int j = i+1; j < n; j++){
cnt[i][j+1] += cnt[i][j];
}
}
for(int i = n; i > 1; i--){
for(int j = i+1; j <= n; j++){
cnt[i-1][j] += cnt[i][j];
}
}
for(int i = 1; i <= k; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = 1e9;
}
}
for(int i = 1; i <= n; i++) dp[1][i] = cnt[1][i];
for(int i = 2; i <= k; i++) solve(1,n,1,n,i);
cout<<dp[k][n]<<"\n";
}
return 0;
}