Untitled

#include <iostream>
#define max(a, b) (a > b) ? a : b
using namespace std;

int T, N;
int maxPoint, ans;
int arr[15];
int visited[15];

int cal(int index){
	int R = 100;
	int L = 100;
	for(int i = index; i < N; i++){
		if(visited[i] == 0){
			R = i;
			break;
		}
	}
	for(int i = index; i >= 0; i--){
		if(visited[i] == 0){
			L = i;
			break;
		}
	}
	if(L != 100 && R != 100){
		return arr[L] * arr[R];
	}else if(L == 100 && R != 100){
		return arr[R];
	}else if(L != 100 && R == 100){
		return arr[L];
	}else{
		return arr[index];
	}
}

void backtrack(int k){
	if(k == N - 2){
		int tmp = 0;
		for(int i = 0; i < N; i++){
			if(visited[i] == 0){
				tmp = max(tmp, arr[i]);
			}
		}
		ans += 2*tmp;
		if(ans > maxPoint){
			maxPoint = ans;
		}
		ans -= 2*tmp;
		return;
	}
	for(int i = 0; i < N; i++){
		if(visited[i] == 0){
			visited[i] = 1;
			int add = cal(i);
			ans += add;
			backtrack(k + 1);
			ans -= add;
			visited[i] = 0;
		}
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N;
		for(int i = 0; i < N; i++){
			cin >> arr[i];
			visited[i] = 0;
		}
		maxPoint = 0;
		ans = 0;

		backtrack(0);
		cout << "Case #" << tc << endl;
		cout << maxPoint << endl;
	}
	return 0;
}