#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define INF 10000

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

const int MAXN =  + ;

int n,m;

int dp[][];

int a[],sum[];

int solve(int i,int j)

{

    int& ans = dp[i][j];

    if(ans!=-) return ans;

    if(i>=j) return ;

    ans = <<;

    for(int k = ;k<=j-i+;k++)

    {

        ans = min(ans,solve(i+,i+k-)+solve(i+k,j) + (k-)*a[i] + (sum[j]-sum[i+k-])*k);

    }

    return ans;

}

int main()

{

    int i,j;

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n;

        sum[]=;

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

        {

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

            sum[i]=sum[i-]+a[i];

        }

        mem(dp,-);

        pf("%d\n",solve(,n));

    }

    return ;

}

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <cctype>

#include <vector>

#include <iterator>

#include <set>

#include <map>

#include <sstream>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define spf sprintf

#define pb push_back

#define debug printf("!\n")

#define INF 10000

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define pqueue priority_queue

const int MAXN =  + ;

int n,m;

int dp[][];

int a[],sum[];

int main()

{

    int i,j;

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n;

        sum[]=;

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

        {

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

            sum[i]=sum[i-]+a[i];

        }

        mem(dp,);

        for(int l = ;l<=n;l++)

        {

            for(i=;i<=n-l+;i++)

            {

                j = i+l-;

                dp[i][j] = <<;

                for(int k = ;k<=l;k++)

                {

                    dp[i][j] = min(dp[i][j],dp[i+][i+k-] + dp[i+k][j] + (k-)*a[i] + (sum[j]-sum[i+k-])*k);

                }

            }

        }

        pf("%d\n",dp[][n]);

    }

    return ;

}