1. #include <cmath>
2. #include <cstdio>
3. #include <vector>
4. #include <iostream>
5. #include <algorithm>
6. using namespace std;
7.  
8. void solve() {
9.     int n;
10.     cin >> n;
11.     vector<int> a(n);
12.     for(int i = 0; i < n; ++i) {
13.         cin >> a[i];
14.     }
15.     int ans = -1;
16.     for(int i = 0; i < n; ++i) {
17.         vector<int> indicies;
18.         for(int j = 0; j < n; ++j) {
19.             if(i != j) {
20.                 indicies.push_back(j);
21.             }
22.         }
23.         do {
24.             vector<bool> taken(n, false);
25.             int sum = 0;
26.             for(int k = 0; k < (int) indicies.size(); ++k) {
27.                 taken[indicies[k]] = true;
28.                 int l = indicies[k] - 1;
29.                 int r = indicies[k] + 1;
30.                 while(l >= 0 and taken[l] == true) {
31.                     l -= 1;
32.                 }
33.                 while(r < n and taken[r] == true) {
34.                     r += 1;
35.                 }
36.                 if(l < 0 and r >= n) {
37.                     sum += a[indicies[k]];
38.                 } else if(l >= 0 and r >= n) {
39.                     sum += a[l];
40.                 } else if(l < 0 and r < n) {
41.                     sum += a[r];
42.                 } else {
43.                     sum += a[l] * a[r];
44.                 }
45.             }
46.             sum += a[i];
47.             ans = max(ans, sum);
48.  
49.         } while(next_permutation(indicies.begin(), indicies.end()));
50.     }
51.    
52.     cout << ans << 'n';
53. }
54.  
55. int main() {
56.     /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
57.    int t;
58.    cin >> t;
59.    while(t--) {
60.        cout << "#" << t + 1 << ' ';
61.        solve();
62.    }
63.     return 0;
64. }
65.  
66.  
67. /*
68.  
69. 10
70. 9
71. 1 2 3 4 5 6 7 8 9
72. 9
73. 1 2 3 4 5 6 7 8 9
74. 9
75. 1 2 3 4 5 6 7 8 9
76. 9
77. 1 2 3 4 5 6 7 8 9
78. 9
79. 1 2 3 4 5 6 7 8 9
80. 9
81. 1 2 3 4 5 6 7 8 9
82. 9
83. 1 2 3 4 5 6 7 8 9
84. 9
85. 1 2 3 4 5 6 7 8 9
86. 9
87. 1 2 3 4 5 6 7 8 9
88. 9
89. 1 2 3 4 5 6 7 8 9
90.  
91. */
92.  
93.  
94. /*
95.  
96. 10
97. 10
98. 1 2 3 4 5 6 7 8 9 10
99. 10
100. 1 2 3 4 5 6 7 8 9 10
101. 10
102. 1 2 3 4 5 6 7 8 9 10
103. 10
104. 1 2 3 4 5 6 7 8 9 10
105. 10
106. 1 2 3 4 5 6 7 8 9 10
107. 10
108. 1 2 3 4 5 6 7 8 9 10
109. 10
110. 1 2 3 4 5 6 7 8 9 10
111. 10
112. 1 2 3 4 5 6 7 8 9 10
113. 10
114. 1 2 3 4 5 6 7 8 9 10
115. 10
116. 1 2 3 4 5 6 7 8 9 10
117.  
118. */