#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int t, n, k;
int fen[N];
vl a;

ll calc (vl &v) {
	multiset <ll> st;
	ll sol = 0;
	for (auto x : v) {
		if (st.empty() || x >= *st.rbegin()) {
			st.insert(x);
		} else {
			ll mx = *st.rbegin();
			st.insert(x);
			st.insert(x);
			st.erase(st.find(mx));
			sol += mx - x;
		}
	}
	return sol;
}

void okreni (vl &v) {
	ll prvi = v[0];
	for (int i = 1; i < (int)v.size(); i++) {
		v[i - 1] = v[i];
	}
	v[(int)v.size() - 1] = prvi;
}

void ubaci (int x, int k) {
	for (; x < N; x += x&-x) fen[x] += k;
}

int upit (int x) {
	int res = 0;
	for (; x > 0; x -= x&-x) res += fen[x];
	return res;
}

int parnost (vl &v) {
	vector < pair <ll, int> > r;
	for (int i = 0; i < n; i++) {
		r.push_back({v[i], i + 1});
	}
	sort(r.begin(), r.end());
	ll cnt = 0;
	for (int i = 0; i <= n; i++) {
		fen[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		int val = r[i].second;
		cnt += upit(val);
		ubaci(val, 1);
	}
	return cnt % 2;
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> k;
		a.resize(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		if (k == 1) {
			cout << calc(a) << '\n';
		} else if (k == n) {
			ll sol = LLINF;
			for (int i = 0; i < n; i++) {
				sol = min(sol, calc(a));
				okreni(a);
			}
			cout << sol << '\n';
		} else if (k % 2 == 0) {
			cout << 0 << '\n';
		} else if (parnost(a) == 0) {
			cout << 0 << '\n';
		} else {
			ll sol = LLINF;
			sort(a.begin(), a.end());
			for (int i = 1; i < n; i++) {
				sol = min(sol, a[i] - a[i - 1]);
			}
			cout << sol << '\n';
		}
	}
	return 0;
}