#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
int n, k, a[N];
int bt[N];
inline void Add(int x, int y) {
    while (x) {
        bt[x] += y;
        x -= x & -x;
    }
}
inline int Ask(int x) {
    int ans = 0;
    while (x <= n) {
        ans += x;
        x += x & -x;
    }
    return ans;
}
inline int Solve() {
    multiset<int> st;
    int f0 = 0, delta0 = 0;
    for (int i = 1; i <= n; ++i) {
        f0 += a[i];
        st.insert(a[i]);
        st.insert(a[i]);
        delta0 -= 1;
        while (st.size() > -delta0) st.erase(--st.end());
    }
    int x = 0, fx = f0, delta = delta0;
    for (auto nx : st) {
        fx += delta * (nx - x);
        ++delta;
        x = nx;
    }
    return fx;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int Case;
    cin >> Case;
    while (Case--) {
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        if (k == 1) {
            cout << Solve() << '\n';
            continue;
        }
        if (k == n) {
            int ans = 1e15;
            for (int r = 0; r < n; ++r) {
                ans = min(ans, Solve());
                rotate(a + 1, a + 2, a + n + 1);
            }
            cout << ans << '\n';
            continue;
        }
        if (~k & 1) {
            cout << 0 << '\n';
            continue;
        }
        vector<int> V(a + 1, a + n + 1);
        sort(V.begin(), V.end());
        int sm = 0;
        for (int i = 1; i <= n; ++i) {
            int k = lower_bound(V.begin(), V.end(), a[i]) - V.begin() + 1;
            sm += Ask(k + 1);
            Add(k, 1);
        }
        for (int i = 1; i <= n; ++i) bt[i] = 0;
        int mn = 1e9;
        for (int i = 0; i + 1 < n; ++i) mn = min(mn, V[i + 1] - V[i]);
        cout << (sm & 1 ? mn : 0) << '\n';
    }
    return 0;
}