#include<bits/stdc++.h>
#define int long long
using namespace std;
using E=long long;

void solve(){
	int n;
	cin>>n;
	priority_queue<pair<E,int>,vector<pair<E,int>>,greater<>> pq;
	multiset<pair<int,E>> st;
	for(int i=0; i<n; i++){
		int x;
		cin>>x;
		st.insert(make_pair(i,x));
		pq.push(make_pair(x,i));
	}
	
	E ans=0;
	vector<int> stt(n+1);
	while(pq.size()){
		int u=pq.top().second; pq.pop();
		if(stt[u]) continue;
		auto pnt=st.lower_bound(make_pair(u,0));
		auto pnt1=(pnt==st.begin()?prev(st.end()):prev(pnt));
		auto pnt2=(next(pnt)==st.end()?st.begin():next(pnt));
		ans+=pnt->second;
		if(pnt1->second>pnt2->second){
			st.insert(make_pair(pnt1->first,pnt1->second+pnt->second));
			pq.push(make_pair(pnt1->second+pnt->second,pnt1->first));
			stt[pnt1->first]=stt[pnt->first]=1;
			st.erase(pnt1);
			st.erase(pnt);
		}
		else{
			st.insert(make_pair(pnt2->first,pnt2->second+pnt->second));
			pq.push(make_pair(pnt2->second+pnt->second,pnt2->first));
			stt[pnt2->first]=stt[pnt->first]=1;
			st.erase(pnt2);
			st.erase(pnt);
		}
	}
	
	cout<<ans<<'\n';
}

signed main(){
	
	cin.tie(0),cout.tie(0)->sync_with_stdio(false);
	
	int T;
	cin>>T;
	while(T--) solve();
	
	return 0;
}