#include<bits/stdc++.h>
using namespace std;
constexpr int M=3e5+5,inf=0x3f3f3f3f;
int n,cnt,a[M],f[M],tmp[M],pos[M];
bool vis[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void solve(){
	n=cnt=read();long long ans=0;
	for (int i=1;i<=n;i++) a[i]=read(),f[i]=i;
	while (cnt>1){
		for (int i=1;i<=n;i++) tmp[i]=inf,vis[i]=find(i)==i;
		int max1=a[1],max2=-inf,pos1=find(1),pos2=0;
		for (int i=2;i<=n;i++){
			const int bel=find(i);
			if (pos1==bel) { if (a[i]-max2<tmp[bel]) tmp[bel]=a[i]-max2,pos[bel]=pos2; }
			else { if (a[i]-max1<tmp[bel]) tmp[bel]=a[i]-max1,pos[bel]=pos1; }
			if (a[i]>max1){
				if (bel==pos1) max1=a[i];
				else max2=max1,pos2=pos1,max1=a[i],pos1=bel;
			}
			else if (a[i]>max2&&bel!=pos2)
				max2=a[i],pos2=bel;
		}
		int min1=a[n],min2=inf;pos1=find(n);pos2=0;
		for (int i=n-1;i;i--){
			const int bel=find(i);
			if (pos1==bel) { if (min2-a[i]<tmp[bel]) tmp[bel]=min2-a[i],pos[bel]=pos2; }
			else { if (min1-a[i]<tmp[bel]) tmp[bel]=min1-a[i],pos[bel]=pos1; }
			if (a[i]<min1){
				if (bel==pos1) min1=a[i];
				else min2=min1,pos2=pos1,min1=a[i],pos1=bel;
			}
			else if (a[i]<min2&&bel!=pos2)
				min2=a[i],pos2=bel;
		}
		for (int i=1;i<=n;i++)
			if (vis[i]){
				if (find(i)==find(pos[i])) continue;
				ans+=tmp[i];f[find(i)]=find(pos[i]);cnt--;
			}
	}
	printf("%lld\n",ans);
}
int main(){int T=read(); while (T--) solve(); return 0;}