#include <bits/stdc++.h>

using namespace std;

using ll = long long;

//  by https://codeforces.com/profile/Nyaan
//  example submission:
//  https://codeforces.com/contest/1603/submission/133688639
template <uint32_t mod>
struct LazyMontgomeryModInt {
  using mint = LazyMontgomeryModInt;
  using i32 = int32_t;
  using u32 = uint32_t;
  using u64 = uint64_t;
 
  static constexpr u32 get_r() {
    u32 ret = mod;
    for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
    return ret;
  }
 
  static constexpr u32 r = get_r();
  static constexpr u32 n2 = -u64(mod) % mod;
  static_assert(r * mod == 1, "invalid, r * mod != 1");
  static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
  static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
 
  u32 a;
 
  constexpr LazyMontgomeryModInt() : a(0) {}
  constexpr LazyMontgomeryModInt(const int64_t &b)
      : a(reduce(u64(b % mod + mod) * n2)){};
 
  static constexpr u32 reduce(const u64 &b) {
    return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
  }
 
  constexpr mint &operator+=(const mint &b) {
    if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
    return *this;
  }

  constexpr mint &operator++() {
    return *this += 1;
  }

  constexpr mint operator++(int) {
    auto ret = *this;
    *this += 1;
    return ret;
  }

  constexpr mint &operator-=(const mint &b) {
    if (i32(a -= b.a) < 0) a += 2 * mod;
    return *this;
  }

  constexpr mint &operator--() {
    return *this -= 1;
  }

  constexpr mint operator--(int) {
    auto ret = *this;
    *this -= 1;
    return ret;
  }
 
  constexpr mint &operator*=(const mint &b) {
    a = reduce(u64(a) * b.a);
    return *this;
  }
 
  constexpr mint &operator/=(const mint &b) {
    *this *= b.inv();
    return *this;
  }
 
  constexpr friend mint operator+(mint a, const mint &b) { return a += b; }
  constexpr friend mint operator-(mint a, const mint &b) { return a -= b; }
  constexpr friend mint operator*(mint a, const mint &b) { return a *= b; }
  constexpr friend mint operator/(mint a, const mint &b) { return a /= b; }
  constexpr friend bool operator==(mint const& a, const mint &b) {
    return (a.a >= mod ? a.a - mod : a.a) == (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr friend bool operator!=(mint const& a, const mint &b) {
    return (a.a >= mod ? a.a - mod : a.a) != (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr friend bool operator<(mint const& a, const mint &b) {
    return (a.a >= mod ? a.a - mod : a.a) < (b.a >= mod ? b.a - mod : b.a);
  }
  constexpr mint operator-() const { return mint() - mint(*this); }
 
  constexpr mint power(int64_t n) const {
    mint ret(1), mul(*this);
    if (n < 0) {
      n = -n;
      mul = mul.inv();
    }
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  
  constexpr mint inv() const { return power(mod - 2); }
 
  friend ostream &operator<<(ostream &os, const mint &b) {
    return os << b.get();
  }
 
  friend istream &operator>>(istream &is, mint &b) {
    int64_t t;
    is >> t;
    b = LazyMontgomeryModInt<mod>(t);
    return (is);
  }
  
  constexpr u32 get() const {
    u32 ret = reduce(a);
    return ret >= mod ? ret - mod : ret;
  }

  constexpr explicit operator int() const {
    return int(get());
  }

  constexpr explicit operator bool() const {
    return bool(get());
  }
 
  static constexpr u32 get_mod() { return mod; }
};
 
template <typename T>
struct Binomial {
  vector<T> f, g, h;
  Binomial(int MAX = 0) : f(1, T(1)), g(1, T(1)), h(1, T(1)) {
    extend(MAX + 1);    
  }

  void extend(int m) {
    int n = f.size();

    if (n >= m) {
      return;
    }

    f.resize(m);
    g.resize(m);
    h.resize(m);
    for (int i = n; i < m; i++) f[i] = f[i - 1] * T(i);
    g[m - 1] = f[m - 1].inv();
    h[m - 1] = g[m - 1] * f[m - 2];
    for (int i = m - 2; i >= n; i--) {
      g[i] = g[i + 1] * T(i + 1);
      h[i] = g[i] * f[i - 1];
    } 
  }

  void extend() {
    extend(2 * f.size());
  }
 
  T fact(int i) {
    if (i < 0) return T(0);
    while (i >= (int)f.size()) extend();
    return f[i];
  }
 
  T ifact(int i) {
    if (i < 0) return T(0);
    while (i >= (int)g.size()) extend();
    return g[i];
  }
 
  T inv(int i) {
    if (i < 0) return -inv(-i);
    while (i >= (int)h.size()) extend();
    return h[i];
  }
 
  T C(int n, int r) {
    if (n < 0 || n < r || r < 0) return T(0);
    return fact(n) * ifact(n - r) * ifact(r);
  }
 
  inline T operator()(int n, int r) { return C(n, r); }
 
  template <typename I>
  T multinomial(const vector<I>& r) {
    static_assert(is_integral<I>::value == true);
    int n = 0;
    for (auto& x : r) {
      if(x < 0) return T(0);
      n += x;
    }
    T res = fact(n);
    for (auto& x : r) res *= ifact(x);
    return res;
  }
 
  template <typename I>
  T operator()(const vector<I>& r) {
    return multinomial(r);
  }
 
  T C_naive(int n, int r) {
    if (n < 0 || n < r || r < 0) return T(0);
    T ret = T(1);
    r = min(r, n - r);
    for (int i = 1; i <= r; ++i) ret *= inv(i) * (n--);
    return ret;
  }
 
  T A(int n, int r) {
    if (n < 0 || n < r || r < 0) return T(0);
    return fact(n) * ifact(n - r);
  }
 
  T CR(int n, int r) {
    if (n < 0 || r < 0) return T(0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
// int const MOD = 998244353;
int const MOD = int(1e9 + 7);
using mint = LazyMontgomeryModInt<MOD>;
Binomial<mint> C;

vector<mint> mkpow(mint base, int mx) {
  vector<mint> res(mx + 1);
  res[0] = 1;
  for (int i = 1; i <= mx; ++i) {
    res[i] = res[i - 1] * base;
  }
  return res;
}

string printMint(mint x, int mx = 100) {
  for (int p = -mx; p <= mx; ++p) {
    for (int q = 1; q <= mx; ++q) {
      if (mint(p) * C.inv(q) == x) {
        int pp = p;
        int qq = q;
        int g = gcd(pp, qq);
        pp /= g;
        qq /= g;
        return to_string(pp) + "/" + to_string(qq);
      }
    }
  }
  return "?";
}

void solveTest() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& x : a) {
    cin >> x;
  }
  ll const INF = ll(1e18);

  auto solveRem = [&](int r) -> ll {
    mint kLast = 1;
    mint bLast = 0;
    //  x[i - 1] = kLast * x[n - 1] + bLast
    vector<mint> ks(n);
    vector<mint> bs(n);
    for (int i = 0; i < n; ++i) {
      int diff = a[i] - r;
      if (diff < 0) {
        return INF;
      }
      //  2 * x[i - 1] + x[i] = diff
      //  x[i] = -2 * x[i - 1] + diff
      kLast *= -2;
      bLast *= -2;
      bLast += diff;
      ks[i] = kLast;
      bs[i] = bLast;
    }
    //  kLast * x + bLast = x
    //  bLast = (1 - kLast) * x
    mint P = bLast;
    mint Q = 1 - kLast;
    assert(Q != 0);
    vector<ll> x(n);
    x[n - 1] = int(P / Q);
    for (int i = n - 2; i >= 0; --i) {
      x[i] = int(ks[i] * x[n - 1] + bs[i]);
    }
    ll xMin = INF;
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
      sum += x[i];
      xMin = min(xMin, x[i]);
      ll sub = x[i] + 2 * x[(n + i - 1) % n];
      if (a[i] - sub != r) {
        return INF;
      }
    }
    return sum - xMin * n;
  };

  ll ans = INF;
  for (int r = 0; r < 3; ++r) {
    ans = min(ans, solveRem(r));
  }
  
  ll original_sum = 0;
  for (auto& x : a) {
    original_sum += x;
  }
  
  if (ans == INF) {
    cout << 0 << "\n";
  } else {
    cout << (original_sum - 3 * ans) / n << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t; cin >> t;
  while (t--) {
    solveTest();
  }
  return 0;
}
