#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#pragma GCC target("avx")
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
const ll N=3e5+9;
ll T,n,k,a[N],bit[N],b[N],len,c[N];
void Upd(ll x,ll k){
while(x<=n)bit[x]+=k,x+=(x&(-x));
}
ll Query(ll x){
ll res=0;
while(x)res+=bit[x],x-=(x&(-x));
return res;
}
void solve(){
n=read(),k=read();
rep(i,1,n)a[i]=read();
if(k==1){
ll ans=0;
priority_queue<ll>q;
rep(i,1,n){
ll x=a[i];
q.push(x);
if(q.size()&&q.top()>x)ans+=q.top()-x,q.pop(),q.push(x);
}
write(ans),putchar('\n');
}
else if(k==n){
ll ans=1e16;
rep(st,1,n){
ll res=0;
priority_queue<ll>q;
ll now=st;
rep(i,0,n-1){
ll x=a[now];
now++;
if(now>n)now=1;
q.push(x);
if(q.size()&&q.top()>x)res+=q.top()-x,q.pop(),q.push(x);
}
ans=min(ans,res);
}
write(ans),putchar('\n');
}
else {
if(!(k&1))puts("0");
else {
len=0;
rep(i,1,n)b[i]=a[i];
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;
if(len!=n){
puts("0");
return;
}
rep(i,1,n)c[i]=lower_bound(b+1,b+len+1,a[i])-b;
rep(i,0,n+1)bit[i]=0;
ll cnt=0;
per(i,n,1){
cnt+=Query(c[i]-1);
Upd(c[i],1);
}
if(!(cnt&1))puts("0");
else {
ll ans=1e16;
rep(i,1,n-1)ans=min(ans,b[i+1]-b[i]);
write(ans),putchar('\n');
}
}
}
}
bool Med;
int main(){
cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
T=read();
while(T--)solve();
return 0;
}