#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,bit[100005],p[100005],k;
inline void update(int pre,int x){
	while(pre<=n){
		bit[pre]+=x;
		pre+=(pre&-pre);
	}
}
inline int query(int pre){
	int ans=0;
	while(pre>=1){
		ans+=bit[pre];
		pre-=(pre&-pre);
	}
	return ans;
}
struct node{
	int w,id;
}a[500005];
inline bool cmp(node a,node b){
	if(a.w==b.w){
		return a.id<b.id;
	}
	return a.w<b.w;
}
queue<int>q;
void clear(){
	while(!q.empty()){
		int x=q.front();
		q.pop();
		update(x,-1);
	}
}
int t;
bool check(int x){
	int sum=1,ans=0,r=1,l=1;
	while(r<=n){
		update(p[r],1);
		ans+=(r-l+1)-query(p[r]);
		q.push(p[r]);
		if(ans>x){
			sum++;
			l=r;
			ans=0;
			clear();
			if(sum>k){
				return 0;
			}
		}else{
			r++;
		}
	}
	clear();
	if(sum>k){
		return 0;
	}
	return 1;
}
signed main(){
	cin>>t;
	while(t--){
		memset(bit,0,sizeof(bit));
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			cin>>a[i].w;
			a[i].id=i;
		}
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			p[a[i].id]=i;
		}
		int l=0,r=n*(n-1ll)/2ll;
		while(l+1<r){
			int mid=(l+r)>>1;
			if(check(mid)){
				r=mid;
			}else{
				l=mid;
			}
		}
		cout<<r<<"\n";
	}
	return 0;
}