#include <bits/stdc++.h>

using namespace std;
#define int long long

void solve() {
    int n, k; cin >> n >> k;
    k++;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> inv(n + 2, vector<int>(n + 2));
    for(int i = 1 ; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(a[i] > a[j]) inv[i][j] = 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            inv[i][j] += inv[i - 1][j] + inv[i][j - 1] - 1 * inv[i - 1][j - 1];           
        }
    }
    auto inv_on_range = [&](int a, int b) -> int {
        return inv[b][b] - inv[a - 1][b] - inv[b][a - 1] + inv[a - 1][a - 1];
    };
    const int oo = (int)n * n;
    int lo = 0, hi = oo, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        auto check = [&](int loss) -> pair<int, int> {
            vector<pair<int, int>> dp(n + 1, {oo, 0});
            dp[0] = {0, 0};
            for(int i = 0; i <= n; i++) {
                for(int j = i + 1; j <= n; j++) {
                    // biore (i, j]
                    pair<int, int> para = {dp[i].first + inv_on_range(i + 1, j) + loss, dp[i].second + 1};
                    dp[j] = min(dp[j], para);
                }
            }
            return dp[n];
        };
        auto [gain, used] = check(mid);
        if(used <= k) {
            hi = mid - 1;
            ans = max(ans, gain - used * mid);
        }
        else {
            lo = mid + 1;
        }
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while(t--) solve();
}