Untitled

#include<iostream>
using namespace std;
int n;
int a[11];
int dp[11111];

int max(int a, int b){
  if (a < b) return b;
  return a;
}

int dfs(int bit){
  if (bit == 0) return 0;
  if (dp[bit]) return dp[bit];
  int p = 0;
  int b[11];
  for (int i = 0; i < n; i++){
    if ((bit >> i) & 1) b[p++] = i;
  }
  int mx = 0;
  for (int i = 0; i < p; i++){
    int v;
    if (i - 1 >= 0 && i + 1 < p) v = a[b[i - 1]] * a[b[i + 1]];
    else if (i - 1 >= 0) v = a[b[i - 1]];
    else if (i + 1 < p) v = a[b[i + 1]];
    else v = a[b[i]];
    mx = max(mx, dfs(bit ^ (1 << b[i])) + v);
  }
  dp[bit] = mx;
  return mx;
}

void solve(int test){
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  int lim = 1 << n;
  for (int i = 0;  i < lim; i++) dp[i] = 0;
  cout << "Case #" << test << '\n' << dfs(lim - 1) << '\n';
}

int32_t main(){
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) solve(i);


}