#include <iomanip>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
//#include <multiset>
#include <map>
#include <utility>
#include <numeric>
#include "queue"
#include <cassert>
#ifndef __clang__
#include <bits/stdc++.h>
#endif
using namespace std;
constexpr int mod = 998244353;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define debugf(s, ...) fprintf(stderr, "(" #__VA_ARGS__ ") " s "\n", __VA_ARGS__)

#define rs ranges::

using i64 = int64_t;
using i128 = __int128;

void solve(int tc) {
    int n;
    cin >> n;

    vector<int> init(n);

    for (auto &e: init) {
        cin >> e;
    }

    auto check = [&init, n, tc] (i64 res) -> bool {
        auto cp = init;
        for (auto &e: cp) {
            if (e < res)
                return false;
            e -= res;
        }

        array<i128, 2> linfunc{i128(0), i128(1)};

        for (int j = 1; j < 31; ++j) {
            linfunc[0] *= -2;
            linfunc[1] *= -2;
            linfunc[0] += cp[j % n];

//            debugf("%lld %lld", i64(linfunc[0]), i64(linfunc[1]));
        }

        if (linfunc[0] >= (1 << 30)) return false;

        i128 b = (linfunc[0] >= 0) ? 0 : (-linfunc[0] + linfunc[1] - 1) / linfunc[1];
//        debugf("%d %lld %lld", tc, res, i64(b));
        i128 cur = b;
        for (int i = 1; i <= n; ++i) {
            cur = cp[i % n] - 2 * cur;
            if (cur < 0) {
                return false;
            }
        }
        if (cur != b) return false;
        return true;
    };

    i64 best_ans = 2e9;
    for (int x = 0; x < 3; ++x) {
        i64 lo = 0;
        i64 hi = 334'000'000;
        if (!check(x)) continue;

        while (lo < hi - 1) {
            i64 me = (lo + hi) / 2;
            if (check(x + me * 3)) lo = me;
            else hi = me;
        }

        best_ans = min(best_ans, x + 3 * lo);
    }

    if (best_ans == i64(2e9)) {
        cout << 0 << '\n';
    } else {
        cout << best_ans << '\n';
    }
}
signed main() {
#ifndef __clang__
    cin.tie(0);
    ios_base::sync_with_stdio(0);
#endif

    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) solve(i);
    //pointd p = {5.7, -3};
}
