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

const int N=3e5+1e3+7;

using pii=pair<int,int>;

int T,n,x[N];

int fa[N];

int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&x[i]),fa[i]=i;
		long long ans=0;
		x[0]=1e9;
		while(1)
		{
			bool ok=1;
			for(int i=1;i<=n;i++)
				if(find(i)!=find(1))
					ok=0;
			if(ok)
				break;
			vector<pii>e;
			int mn=0,smn=0;

			for(int i=n;i>=1;i--)
			{
				int f=find(i);
				if(mn!=0)
				{
					if(find(mn)!=f)
						e.push_back({i,mn});
					else if(smn!=0)
						e.push_back({i,smn});
				}
				int c=i;
				if(x[c]<x[mn])
					swap(mn,c);
				if(x[c]<x[smn])
					swap(smn,c);
				if(find(smn)==find(mn))
					swap(c,smn);
			}

			vector<int>me(n+1,1e9);
			vector<pii>cho(n+1);
			for(auto [a,b]:e)
			{
				int fx=find(a),fy=find(b);
				if(me[fx]>x[b]-x[a])
					me[fx]=x[b]-x[a],cho[fx]={a,b};
				if(me[fy]>x[b]-x[a])
					me[fy]=x[b]-x[a],cho[fy]={a,b};
			}
			for(int i=1;i<=n;i++)
			{
				if(me[i]>1e8)
					continue;
				auto [a,b]=cho[i];
				int fx=find(a),fy=find(b);
				if(fx==fy)
					continue;
				fa[fx]=fy;
				ans+=x[b]-x[a];
			}
		}
		printf("%lld\n",ans);
	}
}