Quake Live Team Split

Quake Live is a first person shooter that supports several match types. The most popular one is the 4 on 4 team deathmatch. Eight players enter, they are split into two teams of four, and the teams fight to the death. The team whose players all die first loses.

The server keeps a match history for every player and estimates each player's skill level from it, as an integer between 1 and 1000. To keep a match as fair as possible, the server looks at the skill levels of the players who connect and splits them into two teams so that the difference between the sum of skills on team A and the sum of skills on team B is as small as possible.

You want to check that the server really does this. Given the skill levels of the players who enter, find the smallest possible difference between the two team totals. The two teams always have the same number of players.

The first line contains the number of test cases $T$. Each of the next $T$ lines describes one test case. A line starts with the number of players $N$, and the remaining $N$ integers on that line are the skill levels of the players, given in no particular order.

Limits

• $1 \le T \le 100$
• $N$ is even and $2 \le N \le 16$
• every skill level is an integer between 1 and 1000

For each test case, print one line in the form Case #X: Y, where $X$ is the test case number starting from 1 and $Y$ is the smallest possible difference between the sum of skill levels on team A and the sum of skill levels on team B.