#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = -1;
    for(int i = 0; i < n; ++i) {
        vector<int> indicies;
        for(int j = 0; j < n; ++j) {
            if(i != j) {
                indicies.push_back(j);
            }
        }
        do {
            vector<bool> taken(n, false);
            int sum = 0;
            for(int k = 0; k < (int) indicies.size(); ++k) {
                taken[indicies[k]] = true;
                int l = indicies[k] - 1;
                int r = indicies[k] + 1;
                while(l >= 0 and taken[l] == true) {
                    l -= 1;
                }
                while(r < n and taken[r] == true) {
                    r += 1;
                }
                if(l < 0 and r >= n) {
                    sum += a[indicies[k]];
                } else if(l >= 0 and r >= n) {
                    sum += a[l];
                } else if(l < 0 and r < n) {
                    sum += a[r];
                } else {
                    sum += a[l] * a[r];
                }
            }
            sum += a[i];
            ans = max(ans, sum);
 
        } while(next_permutation(indicies.begin(), indicies.end()));
    }
   
    cout << ans << 'n';
}
 
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
   int t;
   cin >> t;
   while(t--) {
       cout << "#" << t + 1 << ' ';
       solve();
   }
    return 0;
}
 
 
/*
 
10
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9
9
1 2 3 4 5 6 7 8 9

*/


/*

10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10

*/