/*
* UVa 10482 Algorithm DP
* http://online-judge.uva.es/p/v104/10482.html
* 如果他不是分给三个小孩而是分给k个小孩该怎么做呢????
* 不知道, 以我现在的思路就是用k-1dim数组, 那也太Brute了, 这个问题值得思考啊...
* 努力AC吧， 虽然累，但是值得，总比去追追不到的要实在，虽然累总比痛苦好．
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX 33
#define TMAX 650
struct node {
int flag;
int mark[MAX];
int f[TMAX];
};
struct node Thrf[TMAX];
int candy[MAX];
int maxl(int a, int b, int c)
{
int t = a > b ? a : b;
t = t > c ? t : c;
return t;
}
int minl(int a, int b, int c)
{
int t = a < b ? a : b;
t = t < c ? t : c;
return t;
}
int cmp(const void *a, const void *b)
{
const int *s1 = (const int *)a;
const int *s2 = (const int *)b;
if (*s1 > *s2) return 1;
return -1;
}
int main(void)
{
int i, j, k, l, n, t, tmp, cas, total, min;
scanf("%d", &t);
for (cas = 1; cas <= t; cas++) {
scanf("%d", &n);
for (i = 1, total = 0; i <= n; i++) {
scanf("%d", &candy[i]);
total += candy[i];
}
qsort(candy + 1, n, sizeof(int), cmp);
// initialize...
for (i = 0; i <= total; i++) {
Thrf[i].flag = 0;
memset(Thrf[i].mark, 0, sizeof(Thrf[i].mark));
memset(Thrf[i].f, 0, sizeof(Thrf[i].f));
}
Thrf[0].flag = 1;
k = 0;
for (i = 1; i <= n; i++) {
// 将第i种糖加进来的时候。
for (j = k; j >= 0; j--) {// && Thrf[j + candy[i]].flag == 0
if (Thrf[j].flag) {
Thrf[j + candy[i]].flag = 1;
for (l = 1; l <= n; l++) Thrf[j + candy[i]].mark[l] = Thrf[j].mark[l];
Thrf[j + candy[i]].mark[i] = 1;
}
}
k += candy[i];
}
for (l = 0; l <= total; l++) {
if (Thrf[l].flag == 0) continue;
Thrf[l].f[0] = 1;
k = 0;
for (i = 1; i <= n; i++) {
if (Thrf[l].mark[i]) continue;
// 将第i类糖果加到里面去。
for (j = k; j >= 0; j--) {
if (Thrf[l].f[j]) Thrf[l].f[j + candy[i]] = 1;
}
k += candy[i];
}
}
min = INT_MAX;
for (i = 0; i <= total; i++) {
if (Thrf[i].flag) {
for (j = 0; j <= total - i; j++) {
if (Thrf[i].f[j]) {
tmp = maxl(i, j, total - i - j) - minl(i, j, total - i - j);
if (min > tmp) min = tmp;
}
}
}
}
printf("Case %d: %d\n", cas, min);
}
return 0;
}