#include<bits/stdc++.h>
using namespace std;
int main()
{
#define int long long
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		vector<int> a(n+5);
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		long long ans=0;
		int f1=0,f2[2]={0ll,0ll};
		for(int i=1;i<=n;i++)
		{
//			cerr<<"pos "<<i<<' '<<a[i]<<' '<<f1<<' '<<f2[i%2]<<' '<<f2[(i+1)%2]<<endl;
			int d2=max(max(a[i]-f1,0ll)-max(a[i+1]-f1-f2[(i+1)%2],0ll),min(max(a[i]-f1,0ll),f2[i%2]));
			int d1=max(min(max(a[i]-f2[i%2],0ll),max(a[i+1]-f2[(i+1)%2],0ll)),min(a[i],f1));
			if(d2<=f2[i%2])f2[i%2]=d2;
			else
			{
//				cerr<<"type 2 add "<<d2-f2[i%2]<<endl;
				ans+=d2-f2[i%2],f2[i%2]=d2;
			}
			if(d1<=f1)f1=d1;
			else
			{
//				cerr<<"type 1 add "<<d1-f1<<endl;
				ans+=d1-f1,f1=d1;
			}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}