#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn 1010

#define maxm 55555

using namespace std;

const int inf=maxn;

int to[maxm],cap[maxm],cost[maxm],next[maxm],first[maxn],edge;

int d[maxn],num[maxn],from[maxn],tag[maxn],TAG=;

int Q[maxm],bot,top;

int n,m,s,t,ans,T,a[maxn];

void _init()

{

    edge=-,s=,t=n+,ans=;

    for (int i=s; i<=t; i++) first[i]=-;

}

void addedge(int U,int V,int W,int C)

{

    edge++;

    to[edge]=V,cap[edge]=W,cost[edge]=C,next[edge]=first[U],first[U]=edge;

    edge++;

    to[edge]=U,cap[edge]=,cost[edge]=-C,next[edge]=first[V],first[V]=edge;

}

bool bfs()

{

    Q[bot=top=]=s,d[s]=,num[s]=inf,from[s]=-,tag[s]=++TAG;

    while (bot<=top){

        int cur=Q[bot++];

        for (int i=first[cur]; i!=-; i=next[i])

            if (cap[i]> && (tag[to[i]]!=TAG || d[cur]+cost[i]<d[to[i]])){

                d[to[i]]=d[cur]+cost[i];

                tag[to[i]]=TAG,

                num[to[i]]=min(num[cur],cap[i]);

                Q[++top]=to[i];

                from[to[i]]=i;

            }

    }

    if (tag[t]!=TAG || num[t]<=) return false;

    ans+=num[t]*d[t];

    for (int i=t; from[i]!=-; i=to[from[i]^])

        cap[from[i]]-=num[t],cap[from[i]^]+=num[t];

    return true;

}

int main()

{

    scanf("%d",&T);

    while (T--)

    {

        scanf("%d",&n);

        _init();

        for (int i=; i<=n; i++) {

            scanf("%d",&a[i]);

            addedge(s,i,a[i],);

            addedge(i,t,,);

            if (i<n) addedge(i,i+,inf,);

            if (i>) addedge(i,i-,inf,);

        }

        addedge(,n,inf,);

        addedge(n,,inf,);

        while (bfs()) ;

        printf("%d\n",ans);

    }

    return ;

}