#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
constexpr ll INF = 1e16 + 1;

ll solver(const vector<ll> &a) {
    ll ans = 0;
    priority_queue<ll> Q;
    Q.push(a[0]);
    for (ll i = 1; i < a.size(); ++i) {
        ll t = a[i];
        Q.push(t);
        if (Q.top() > t) {
            ans += Q.top() - t;
            Q.pop();
            Q.push(t);
        }
    }
    return ans;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (auto &i: a)cin >> i;
    if (k == 1) {
        cout << solver(a) << "\n";
        return;
    }
    if (k == n) {
        ll res = INF;
        deque<ll> d(a.begin(), a.end());
        for (int i = 0; i < n; ++i) {
            d.push_back(d.front());
            d.pop_front();
            res = min(res, solver(vector<ll>(d.begin(), d.end())));
        }
        cout << res << "\n";
        return;
    }
    if (k >= 3 && (k - 3) % 2 == 0) {
        vector<pl> b;
        for (ll i = 0; i < n; ++i) {
            b.push_back({a[i], i});
        }
        sort(b.begin(), b.end());
        ll z = 0;
        for (ll i = 0; i < n; ++i) {
            z ^= b[i].second != i;
        }
        ll res = (!z ? INF : 0);
        for (ll i = 1; i < n; ++i)res = min(res, b[i].first - b[i - 1].first);
        cout << res << "\n";
    } else {
        cout << "0\n";
    }

}

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