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

using namespace __gnu_pbds;
using namespace std;

#define mxn 1e5+5
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define endl '\n'
typedef long long ll;
using pii = pair<int,int>;
using tlll = tuple<ll,ll,ll>;

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


int solve(){
    int n, k;
    cin >> n >> k;

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

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

        tlll ans = {-1,-1, -1};

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

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

            dp[i] = dp[i+1] + maiores_antes - menores_depois;
            ans = max(ans, make_tuple(ll(dp[i]),ll(i), *msa.rbegin()));
        }

        for(int i = get<1>(ans); i < n; i++) {
            a[i] += get<2>(ans);
        }
    }

    ll ans = 0;
    multiordered_set ms;
    map<ll, int> occur;
    
    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';

    return 0;
}

int main(){
    fastio;

    int t; 
    cin >> t;

    while(t--){
        solve();
    }

    return 0;
}