#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

int n, k, b[100005];
pii a[100005];

void add(int x,int y)
{
    while(x <= n)
    {
        b[x] += y;
        x += x & -x;
    }
}

int query(int x)
{
    int res = 0;
    while(x)
    {
        res += b[x];
        x -= x & -x;
    }
    return res;
}

int clear(int l, int r)
{
    for(int i=l; i<=r; i++)
        add(a[i].second, -1);
}

bool check(int x)
{
    int cnt = 0, last = 0, sum = 0;
    for(int i=1; i<=n; i++)
    {
        add(a[i].second, 1);
        sum += i - last - query(a[i].second);
        if(sum > x || i == n)
        {
            clear(last + 1, i - 1);
            last = i - 1;
            cnt++;
            sum = 0;
        }
    }
    clear(last + 1, n);
    return cnt <= k;
}

void solve()
{
    cin >> n >> k;
    for(int i=1; i<=n; i++)
        cin >> a[i].first, a[i].second = i;
    auto cmp = [](pii x, pii y) {
        if(x.first == y.first)
            return x.second < y.second;
        return x.first < y.first;
    };
    sort(a+1, a+n+1, cmp);
    int l = 1, r = n * (n - 1) / 2, ans;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans << endl;
}

signed main()
{
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}