#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;

const int maxn = 510000;
const int maxd = 20;

int n;
int a[maxn];
int t[maxn],tp;

struct node
{
	int c,lc,rc;
	node(){ c=lc=rc=0; }
}seg[maxn*maxd]; int root[maxn],tot;
int newnode()
{
	seg[++tot]=node();
	return tot;
}
int loc;
int ins(int x,const int l,const int r)
{
	int y=newnode();
	seg[y]=seg[x];
	seg[y].c++;
	if(l!=r)
	{
		int mid=(l+r)>>1;
		if(loc<=mid) seg[y].lc=ins(seg[y].lc,l,mid);
		else seg[y].rc=ins(seg[y].rc,mid+1,r);
	}
	return y;
}
int queryk(const int x,const int y,const int l,const int r,int k)
{
	if(l==r) return l;
	int mid=(l+r)>>1;
	if( seg[seg[y].lc].c-seg[seg[x].lc].c>=k ) return queryk(seg[x].lc,seg[y].lc,l,mid,k);
	else 
	{
		k-=seg[seg[y].lc].c-seg[seg[x].lc].c;
		return queryk(seg[x].rc,seg[y].rc,mid+1,r,k);
	}
}
/*
struct node
{
	int n1,n2;
	priority_queue<int>qx;
	priority_queue<int, vector<int> ,greater<int> >qn;
	
}
vector<node>;
typedef __gnu_pbds::tree< int, __gnu_pbds::null_type,
				  less< int >, __gnu_pbds::rb_tree_tag,
				  __gnu_pbds::tree_order_statistics_node_update >
				  PB;
vector<PB>V;*/

int calc(int l,int r)
{
	int num=r-l+1;
	return queryk( root[l-1],root[r],1,n,(num+1)/2 );
//	return *V[i].find_by_order( (num+1)/2-1 );
}
pair<int,int>ai[maxn];

ll solve()
{
	/*{
		vector<PB>_;
		V.swap(_);
		PB temp; V.push_back(temp);
	}*/
//	V[0].insert(1);
//	V[0].insert(2);
//	cerr<< (*V[0].find_by_order(0))<<endl;
	tot=0;
	
	tp=0;
	for(int i=1;i<=n;i++)
	{
		t[++tp]=i;
		loc=a[i]; root[i]=ins(root[i-1],1,n);
//		PB ti; ti.insert(a[i]);
//		V.push_back(ti);
		
		while(tp>1)
		{
			ll k1= calc(t[tp-1],t[tp]-1);
			ll k2= calc(t[tp],i);
			/*
			cerr<<"tp-1:  ";
			for(int k=0;k<(int)V[tp-1].size();k++) cerr<<*V[tp-1].find_by_order(k)<<' ';
			cerr<<endl;
			cerr<<"tp:    ";
			for(int k=0;k<(int)V[tp].size();k++) cerr<<*V[tp].find_by_order(k)<<' ';
			cerr<<endl;
			*/
			if(k1>k2) 
			{
			//	V[tp-1].join(V[tp]);
			//	V.pop_back();
				tp--;
				/*cerr<<"merge: ";
				for(int k=0;k<(int)V[tp].size();k++) cerr<<*V[tp].find_by_order(k)<<' ';
				cerr<<endl;*/
			}
			else break;
		}
	}
	t[tp+1]=n+1;
	
	ll ret=0;
	int now=0;ll mid;
	for(int i=1;i<=n;i++)
	{
		if(i>=t[now+1] && now<tp) now++, mid=calc(t[now],t[now+1]-1);
		ret+= abs( ai[ a[i] ].first - ai[mid].first );
	}
	return ret;
}
int sum[maxn];
void add(int x,int c)
{
	for(;x<=n;x+=lowbit(x)) sum[x]+=c;
}
int query(int x)
{
	int re=0;
	for(;x;x-=lowbit(x)) re+=sum[x];
	return re;
}

int getmid(int l,int r)
{
	vector<int>V;
	for(int i=l;i<=r;i++) V.push_back(a[i]);
	sort(V.begin(),V.end());
	int num=r-l+1;
	return V[ (num+1)/2-1 ];
}
int f[100][100];
ll solve2()
{
	f[0][0]=0;
	for(int i=1;i<=n;i++) 
	{
		for(int c=0;c<=n;c++) f[i][c]=LLONG_MAX;
		for(int j=0;j<i;j++) 
		{
			ll cc=0;
			int mid=getmid(j+1,i);
			for(int k=j+1;k<=i;k++)
			{
				cc+= abs( ai[mid].first-ai[ a[k] ].first );
			}
			for(int c=0;c<=mid;c++) if(f[j][c]!=LLONG_MAX)
			{
				f[i][mid]=min(f[i][mid], f[j][c]+cc);
			}
			
		}
	}
	int ans=LLONG_MAX;
	for(int c=1;c<=n;c++) ans=min(ans,f[n][c]);
	return ans;
}

signed main()
{
	/////////////////////////////////////////////////
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	mt19937 mt((unsigned long long)(new char));
	
	int Tcase=1000;
	cin>>Tcase;
	while(Tcase--)
	{
		int K=1;
		n=20;
		cin>>n>>K;
		for(int i=1;i<=n;i++) 
		{
			a[i]=mt()%1000+1;
			cin>>a[i];
		}
		
		//cerr<<n<<endl;
		//for(int i=1;i<=n;i++) cerr<<a[i]<<' ';
		//cerr<<endl;
		
		for(int i=1;i<=n;i++)
		{
			ai[i]=make_pair(a[i],i);
		}
		sort(ai+1,ai+n+1);
		for(int i=1;i<=n;i++) a[ai[i].second]=i;
		
		if(K==1)
		{
			ll c1=solve(), c2=solve2();
			assert( c1==c2 );
			cout<<solve()<<'\n';
		}
		else if(K==n)
		{
			int ans=LLONG_MAX;
			for(int d=0;d<n;d++)
			{
				rotate(a+1,a+2,a+n+1);
				ans=min(ans, solve());
			}
			cout<<ans<<'\n';
		}
		else
		{
			if(K%2==0) cout<<"0\n";
			else
			{
				int num=0;
				for(int i=1;i<=n;i++) sum[i]=0;
				for(int i=1;i<=n;i++)
				{
					num+= (i-1)-query(a[i]);
					add(a[i],1);
				}
				if(num%2==1)
				{
					ll ans=LLONG_MAX;
					for(int i=2;i<=n;i++) ans=min(ans,ai[i].first-ai[i-1].first);
					cout<<ans<<'\n';
				}
				else cout<<"0\n";
			}
		}
	}
	
	return 0;
}