Untitled

#include<iostream>
using namespace std;
int n,a[20],ans,visited[20],vt,vp,gtri;

void bt(int score, int k) {
	if (k == (n - 3)) {
		if (ans < score) {
			ans = score;
			gtri = 0;
			for (int i = 1; i < n - 1; i++) {
				if (a[i] == 0)
					gtri = a[i];
			}
			if (a[0] * a[n - 1] > gtri)
				ans = ans + a[0] * a[n - 1] + gtri;
			else
				ans = ans + 2 * gtri;
		}
		return;
	}
	else {
		for (int i = 1; i < n - 1; i++) {
			if (visited[i] == 0) {
				visited[i] = 1;
				vt = 0, vp = 0;
				for (int j = i - 1; j >= 0; j--) {
					if (visited[j] == 0) {
						vt = a[j];
						break;
					}
				}
				for (int j = i + 1; j <n; j++) {
					if (visited[j] == 0) {
						vp = a[j];
						break;
					}
				}
				if (vt != 0 && vp != 0) {
					score = score + vt*vp;
					k++;
					bt(score, k);
					score = score - vt*vp;
					k--;
				}
				if (vt == 0 && vp != 0) {
					score = score + vp;
					k++;
					bt(score, k);
					score = score - vp;
					k--;
				}
				if (vt != 0 && vp == 0) {
					score = score + vt;
					k++;
					bt(score, k);
					score = score - vt;
					k--;
				}
				visited[i] = 0;
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			visited[i] = 0;
		}
		ans = 0;
		bt(0, 0);
		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}