#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 5;
int t, n, k, a[N], b[N], tree[N], ans;
int lowbit (int x){
	return x & -x;
}
int query (int x){
	int sum = 0;
	while (x){
		sum += tree[x];
		x -= lowbit(x);
	}
	return sum;
}
void update (int x, int val){
	while (x <= n){
		tree[x] += val;
		x += lowbit(x);
	}
	return ;
}
bool check (int x){
	int sum = 0, tot = 1, last = 1;
	for (int i = 1; i <= n; ++i) b[i] = a[i];
	sort (b + 1, b + n + 1);
	int len = unique (b + 1, b + n + 1) - (b + 1);
	for (int i = 1; i <= n; ++i){
		int l = 1, r = len, pos;
		while (l <= r){
			int mid = l + r >> 1;
			if (b[mid] >= a[i]){
				pos = mid;
				r = mid - 1;
			}else l = mid + 1;
		}
		a[i] = pos;
	}
	update (a[1], 1);
	for (int i = 2; i <= n; ++i){
		sum += (query(n) - query(a[i]));
		if (sum > x){
			++tot;
			sum = 0;
			for (int j = last; j < i; ++j) update (a[j], -1);
			last = i;
		}
		update (a[i], 1);
	}
	for (int i = last; i <= n; ++i) update (a[i], -1);
	return tot <= k;
}
signed main (){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> t;
	while (t --){
		cin >> n >> k;
		for (int i = 1; i <= n; ++i) cin >> a[i];
		int l = 0, r = 1e18;
		ans = 0;
		while (l <= r){
			int mid = l + r >> 1;
			if (check(mid)){
				ans = mid;
				r = mid - 1;
			}else l = mid + 1;
		}
		cout << ans << '\n';
	}
	return 0;
}