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

using ll = int64_t;

void solve(){
	int N;
	cin >> N;
	vector<ll> A(N);
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	ll original_sum = 0;
	for (auto& x : A) {
	    original_sum += x;
	}
	ll F = *max_element(A.begin(), A.end());
	ll ans = 0;
	for(ll r : {0, 1, 2}){

		ll s = -1;
		ll e = F + 1;
		ll found = -1;
		while(s + 1 < e){
			ll m = (s + e) / 2;

			ll prv = m;
			int fail = -1;
			for(int i = 0; i < N; i++){
				prv = A[i] - r - 2 * prv;
				if(prv < 0){
					fail = i;
					break;
				}
			}
			if(fail == -1){
				if(prv < m){
					fail = N-1;
				} else if(prv > m){
					fail = N;
				}
			}
			if(fail == -1){
				found = m;
				break;
			}
			if(fail % 2 == 0){
				e = m;
			} else {
				s = m;
			}
		}
		if(found != -1){
			vector<ll> use;
			ll prv = found;
			for(int i = 0; i < N; i++){
				use.push_back(prv);
				prv = A[i] - r - 2 * prv;
			}
			assert(prv == found);
			ll d = *min_element(use.begin(), use.end());
			for(ll& c : use) c -= d;
			ans = (original_sum - 3 * accumulate(use.begin(), use.end(), ll(0))) / N;
		}
	}
	cout << ans << '\n';
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();	
}
