#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int T,n,k;
int tre[N],sum[N];

struct dat{int pos,num;}a[N],tra[N];
bool cmpf(dat x,dat y){return x.num<y.num;}
bool cmps(dat x,dat y){return x.pos<y.pos;}

int lowbit(int x){return x&(-x);}
void add(int x,int num){
	while(x<=n){
		tre[x]+=num;
		x+=lowbit(x);
	}
	return;
}
int query(int x){
	int ans=0;
	while(x){
		ans+=tre[x];
		x-=lowbit(x);
	}
	return ans;
}

bool check(long long len){
	int d,dnum,st;
	dnum=0,d=st=1;
	for(int i=1;i<=n;++i){
		dnum+=query(n)-query(a[i].num);
		if(dnum>len){
			for(int j=st;j<i;++j) add(a[j].num,-1);
			st=i,dnum=0,++d;
			if(d>k) return 0;
		}
		add(a[i].num,1);
	}
	for(int i=st;i<=n;++i) add(a[i].num,-1);
	if(d<=k) return true;
	else return false;
}

int main(void){
	long long l,r,mid;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i].num);
			a[i].pos=i;
		}
		sort(a+1,a+n+1,cmpf);
		for(int i=1;i<=n;++i) a[i].num=i;
		sort(a+1,a+n+1,cmps);
		l=0,r=n*n>>1;
		while(l<r){
			mid=(l+r)>>1;
			if(check(mid)) r=mid;
			else l=mid+1;
		}
		printf("%lld\n",r);
	}
}
/*
2
5 2
1 3 2 5 4
*/