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

#define file "o"
#define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
#define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
#define nl "\n"
#define ss " "
#define pb emplace_back
#define fi first
#define se second
#define sz(s) (int)s.size()
#define all(s) (s).begin(), (s).end()
#define ms(a,x) memset(a, x, sizeof (a))
#define cn continue
#define re exit(0)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll ran(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

inline void rf()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if(fopen(file".inp","r"))
    {
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    }
}

const int mod=998244353;
const int maxn=3e5+15;
const ll inf=1e18;

template<typename T> inline void add(T &x, const T &y)
{
    x+=y;
    if(x>=mod) x-=mod;
    if(x<0) x+=mod;
}

template<typename T> inline bool maxi(T &a, T b)
{
    if(a>=b) return 0;
    a=b; return 1;
}

template<typename T> inline bool mini(T &a, T b)
{
    if(a<=b) return 0;
    a=b; return 1;
}

int n, h[maxn], l[maxn], r[maxn];

void solve()
{
    cin>>n;
    ff(i, 0, n-1) cin>>h[i];
    ff(i, 0, n-1)
    {
        r[i]=0; l[i]=0;
        ff(step, 1, n-1)
        {
            int cur=(i+step)%n, pre=(cur-1+n)%n, nxt;
            r[cur]=max(r[pre], h[pre]);
            cur=(i-step+n)%n, nxt=(cur+1)%n;
            l[cur]=max(l[nxt], h[cur]);
        }
        ll sum=0;
        ff(j, 0, n-1) sum+=min(l[j], r[j]);
        cout<<sum<<ss;
    }
    cout<<nl;
}

signed main()
{
    rf();
    int tt; cin>>tt;
    while(tt--) solve();
    re;
}