143

#include<stdio.h>
#include<string.h>
#include<cmath>
#define MAXN 2147483647
using namespace std;
int N, a[1005] = {};
int awe[1005][1005] = {};
int dp(int L,int R){
    if(L == R)return a[L];
    if(awe[L][R] != 0)return awe[L][R];
    int tmp = MAXN, tmpL, tmpR, count = 0;

    for(int mid = L;mid<R;mid++){
        count = 0;
        for(int i = L;i <= R;i++)count+=a[i];
        tmpL = dp(L, mid), tmpR = dp(mid+1, R);
        if(L!=mid)count+=tmpL;
        if(mid+1!=R)count+=tmpR;
        tmp = count < tmp ? count : tmp;
    }
    awe[L][R] = tmp;
    return tmp;
}
int main(){
    int T,ans;
    for(scanf("%d",&T);T;T--){
        memset(awe,0,sizeof(awe));
        scanf("%d",&N);
        for(int iN = 1;iN <= N;iN++){
            scanf("%d",&a[iN]);
        }
        for(int i=1;i<N;i++)awe[i][i+1]=a[i]+a[i+1];
        ans=dp(1,N);
        printf("%d\n",ans);
    }
}