#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 3e5 + 5, M = 1e9;

int a[N], id[N];
int T, n, k;

int lc[N * 35], rc[N * 35], cnt[N * 35], rt[N], tot;
int st[N], top;

void ins(int &u, int l, int r, int x) {
	if (!u) u = ++tot;
	++cnt[u];
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (mid >= x) ins(lc[u], l, mid, x);
	else ins(rc[u], mid + 1, r, x);
}

int merge(int u, int v, int l, int r) {
	if (!u || !v) return u | v;
	if (l == r) {
		cnt[u] += cnt[v];
		return u;
	}
	int mid = (l + r) >> 1;
	lc[u] = merge(lc[u], lc[v], l, mid);
	rc[u] = merge(rc[u], rc[v], mid + 1, r);
	cnt[u] += cnt[v];
	return u;
}

int query(int u, int l, int r, int need) {
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (cnt[lc[u]] >= need) return query(lc[u], l, mid, need);
	return query(rc[u], mid + 1, r, need - cnt[lc[u]]);
}

int getM(int rt, int flag) {
	int need = (cnt[rt] + 1 + flag) / 2;
	return query(rt, 1, M, need);
}

int b[N];

ll calc() {
	for (int i = 1; i <= tot; i++) lc[i] = rc[i] = cnt[i] = 0;
	tot = top = 0;
	for (int i = 1; i <= n; i++) {
		rt[i] = 0;
		ins(rt[i], 1, M, a[i]);
		while (top && getM(rt[i], 0) < getM(rt[st[top]], 0)) {
			rt[i] = merge(rt[i], rt[st[top]], 1, M);
			--top;
		}
		st[++top] = i;
	}
	ll ans = 0;
	for (int i = 1, j = 1; i <= top; i++) {
		int len = 0;
		while (j <= st[i]) {
			b[++len] = a[j];
			++j;	
		}
		sort(b + 1, b + len + 1);
		int mid = b[(len + 1) / 2];
		for (int k = 1; k <= len; k++) ans += abs(b[k] - mid);
	}
	return ans;
}

bool cmp(int i, int j) {
	return a[i] < a[j];
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		if (k == 1) {
			printf("%lld\n", calc());
			continue;
		}
		if (k == n) {
			ll ans = 1e18;
			for (int i = 1; i <= n; i++) {
				ans = min(ans, calc());
				rotate(a + 1, a + n, a + n + 1);
			}
			printf("%lld\n", ans);
			continue;
		}
		if (k % 2 == 0) {
			printf("0\n");
			continue;
		}
		for (int i = 1; i <= n; i++) id[i] = i;
		sort(id + 1, id + n + 1, cmp);
		int res = 0;
		for (int i = 1; i <= n; i++) {
			if (id[i] != i) {
				swap(id[i], id[id[i]]);
				res ^= 1;
			}
		}
		if (res == 0) {
			printf("0\n");
			continue;
		}
		int minn = 1e9;
		sort(a + 1, a + n + 1);
		for (int i = 1; i < n; i++) minn = min(minn, a[i + 1] - a[i]);
		printf("%d\n", minn);
	}
	return 0;
}