#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,L[500100],sta[500100],top;ll a[500010],dp[500100];
void sol(){
	scanf("%d",&n);
	top=0;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),dp[i]=-1e18;
	dp[1]=0;
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
	dp[j]=max(dp[j],dp[i]+1ll*a[i]*j-1ll*a[j]*i);
	printf("%lld\n",1ll*dp[n]+1ll*n*a[n]-a[1]);
}
int main(){
	int T;cin>>T;while(T--)sol();
	return 0;
}