#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>

#define lowbit(i) (i & (-i))

using namespace std;

typedef long long LL;

const int N = 100010;

int a[N];
int tr[N];
int n, k, len;
vector<int> alls;

int find(int x)
{
    int l = 0, r = len - 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (x < alls[mid]) r = mid - 1;
        else l = mid;
    }
    
    return l + 1;
}

void modify(int x, int c)
{
    for (int i = x; i <= len; i += lowbit(i)) tr[i] += c;
}

LL query(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

bool check(LL mid)
{
    LL cnt = 1, op_pair = 0, siz = 0;
   // cout << mid << endl;
    for (int i = 1; i <= n; i ++ )
    {
        siz ++ ;
        int x = find(a[i]);
        modify(x, 1);
        LL p = siz - query(x);
    //    cout << i << "--->" << p << endl;
        if (op_pair + p > mid)
        {
            memset(tr, 0, sizeof tr);
            modify(x, 1);
            op_pair = 0;
            cnt ++ , siz = 1;
            if (cnt > k) return false;
        }
        else op_pair += p;
    }
    
    return true;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        alls.clear();
        scanf("%d%d", &n, &k);
        
        for (int i = 1; i <= n; i ++ )
        {
            scanf("%d", &a[i]);
            alls.push_back(a[i]);
        }
        
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        len = alls.size();
        
        LL l = 0, r = 1e10;
        while (l < r)
        {
            memset(tr, 0, sizeof tr);
            LL mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        
        printf("%lld\n", l);
    }
}