#include<bits/stdc++.h>
#define maxn 100010
#define int long long
using namespace std;
int n,a[maxn],tree[maxn],tot,b[maxn],k,T;
inline int lowbit(int x){return (x&(-x));}
inline void build(){
	for(int i=1;i<=tot;++i)tree[i]=0;
	return;
}
inline void update(int x,int dt){
	if(x>tot||(x<0))return;
	for(int i=x;i<=tot;i+=lowbit(i))
		tree[i]+=dt;
	return;
}
inline int query(int x){
	int sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum+=tree[i];
	return sum;
}
bool check(long long uid){
	build();
	long long res=1,nows=0,pandoraparadoxxxx=0;
	for(int i=1;i<=n;++i){
		long long maimai=pandoraparadoxxxx-query(a[i]);
		if(maimai+nows>uid){
			res++;
			nows=0;
			build();pandoraparadoxxxx=1;
			update(a[i],1);
		}
		else{
			pandoraparadoxxxx++;
			nows+=maimai;
			update(a[i],1);
		}
	}
	return res<=k;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;++i)cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
	long long l=0ll,r=1ll*n*1ll*(n-1)/2,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	cout<<mid<<'\n';
	return;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}