#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define fastio ios::sync_with_stdio(0), cin.tie(nullptr)

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;

typedef tree<ll,null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> multiordered_set;

int main() {
    fastio;

    int t;
    cin >> t;

    while(t--) {
        int n, k;
        cin >> n >> k;

        vector<ll> a(n);
        for(ll &ai : a) cin >> ai;

        while(k--) {
            vector<int> dp(n+1, 0);
            pll ans = {0,n};
            
            multiordered_set msa, msd;
            map<ll,int> occur_a;
            for(int i = 0; i < n; i++) {
                msa.insert(a[i]);
                occur_a[a[i]]++;
            }

            for(int i = n-1; i >= 0; i--) {
                int menores_depois = msd.order_of_key(a[i]);
                msd.erase(msd.upper_bound(a[i]));

                int maiores_antes = msa.size() - msa.order_of_key(a[i]) - occur_a[a[i]];
                msa.erase(msa.upper_bound(a[i]));
                occur_a[a[i]]--;

                dp[i] = dp[i+1] + maiores_antes - menores_depois;
                ans = max(ans, {dp[i],i});
            }

            for(int i = ans.second; i < n; i++) a[i] += ll(1e10);
        }

        multiordered_set ms;
        map<ll,int> occur;
        ll ans = 0;

        for(int i = 0; i < n; i++) {
            ans += i - ms.order_of_key(a[i]) - occur[a[i]];
            ms.insert(a[i]);
            occur[a[i]]++;
        }

        cout << ans << '\n';
    }
}