题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534
#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int maxn =3e3+5;
const int mod=1e9+7;
const int INF =-100000000;
int f[maxn],n;
ll dp[maxn];///表示剩余i度数的时候满足的最优值是多少
/*
题目大意：给定每个度数对应的权重，
要求构建一棵树，这棵树的权重函数之和，要求最大，
输出最大值是多少。这道题是思维题，前提是要先具备一些树的小知识，
首先度的总量肯定是确定的，2*n-2，
其次每个度只要不超过n-1就行，也就是说，
一个度序列，只要每个不超过n-1,且和为2n-2，
则可以肯定符合这个度序列的树是存在的。那么这样分析过后，就比较像背包问题了。
首先不难想到二维DP形式，
表示用前i个节点剩余j个度的最优值，
然后枚举单个节点用掉的度进行状态转移，
这样来分配度数复杂度是三次方，
但仔细想想答案的贡献好像只和度数的分布有关，
具体哪个度数在哪个点上并无关系，
所以不妨直接枚举度数，来构成度数和一样的序列。
但也有问题，因为这样其实就是有点像求排列了那样，
题目中每个顶点必须都要有至少一个度才行，
这样一个巧妙的预处理就到位了，先把每个点分配一个度，
然后额外的所有度的权重减去F[1]，对于任何一个满足条件的排列来说，
这样的分布都可以回归正确的答案。
分析完后下面就是裸的背包问题了。
*/
ll solve(int ub)
{for(int i=0;i<=ub;i++) dp[i]=INF;dp[0]=0;for(int i=2;i<n;i++)for(int j=0;j+i-1<=ub;j++)dp[i+j-1]=max(dp[j]+f[i],dp[i+j-1]);return dp[ub];
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d",&n); for(int i=1;i<n;i++) scanf("%d",&f[i]);ll ans=n*f[1];for(int i=2;i<=n;i++) f[i]-=f[1];printf("%lld\n",ans+solve(n-2));}return 0;
}