#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(a) (a).begin(),(a).end()
#ifdef DEBUG
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(T x:a)out<<x<<',';
	return out<<']';
}
template<class T>
vector<T> ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#else
#define debug(...) void()
#endif
using LL=__int128;
const int N=3e5+10;
const ll INF=1e18;
int T,n,k,a[N];
ll solve(int l=1,int r=n,int L=0,int R=1e9){
	if(l>r)return 0;
	if(L==R){
		ll sum=0;
		for(int i=l;i<=r;i++)sum+=abs(a[i]-L);
		return sum;
	}
	int mid=(L+R)>>1;
	static ll f[N],g[N];
	f[l-1]=g[r+1]=0;
	for(int i=l;i<=r;i++)f[i]=f[i-1]+abs(a[i]-mid);
	for(int i=r;i>=l;i--)g[i]=g[i+1]+abs(a[i]-mid-1);
	int cur=-1;
	ll mn=INF;
	for(int i=l;i<=r+1;i++){
		ll val=f[i-1]+g[i];
		if(val<mn)mn=val,cur=i;
	}
	return solve(l,cur-1,L,mid)+solve(cur,r,mid+1,R);
}
int cur[N],c[N];
void add(int x,int y){
	for(;x;x^=x&-x)c[x]+=y;
}
int get(int x,int y=0){
	for(;x<=n;x+=x&-x)y+=c[x];
	return y;
}
void get(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	if(k==1){
		printf("%lld\n",solve());
	}else if(k==n){
		ll ans=INF;
		for(int i=1;i<=n;i++){
			ans=min(ans,solve());
			rotate(a+1,a+2,a+1+n);
		}
		printf("%lld\n",ans);
	}else if(k==2)puts("0");
	else{
		iota(cur,cur+1+n,0);
		sort(cur+1,cur+1+n,[&](int x,int y){
			return a[x]<a[y];
		});
		fill(c+1,c+1+n,0);
		ll ans=0;
		for(int i=1;i<=n;i++){
			ans+=get(cur[i]);
			add(cur[i],1);
		}
		if(ans&1){
			ll mn=INF;
			for(int i=1;i<n;i++){
				mn=min(mn,(ll)a[cur[i+1]]-a[cur[i]]);
			}
			printf("%lld\n",mn);
		}else puts("0");
	}
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}