#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 6010;
int T;
int n, m;
int tr1[N], tr2[N];
int a[N], c[N];
int lowbit(int x)
{
    return x & -x;
}
int add(int tr[], int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}
int find(int tr[], int x)
{
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        res += tr[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i], c[i] = 0, tr1[i] = tr2[i] = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int cnt = 0;
            for (int j = 1; j < i; j++)
                if (a[j] > a[i])
                    cnt++;
            c[i] = cnt;
            ans += cnt;
            // cout << c[i] << ' ';
        }
        // cout << endl;

        for (int k = 1; k <= m; k++)
        {
            for (int i = 1; i <= n; i++)
                tr1[i] = tr2[i] = 0;
            int pos = 0, maxv = 0;
            for (int i = n; i; i--)
            {
                if (!c[i])
                    continue;
                add(tr1, c[i], c[i]);
                add(tr2, c[i], 1);
                int res1 = find(tr1, c[i] - 1);
                int res2 = (find(tr2, n) - find(tr2, c[i] - 1)) * c[i];
                if (!pos || maxv < res1 + res2)
                    pos = i, maxv = res1 + res2;
                // cout << ":" << i << ' ' << res1 << ' ' << res2 << ' ' << maxv << endl;
            }
            if (!maxv)
                break;
            ans -= maxv;
            int t = c[pos];
            for (int i = pos; i <= n; i++)
                c[i] = max(0, c[i] - t);
        }
        cout << ans << endl;
    }
    return 0;
}