Quake Live 팀 나누기

Quake Live는 여러 방식의 대전을 지원하는 1인칭 슈팅 게임이다. 그중 가장 인기 있는 방식은 4대4 팀 데스매치다. 여덟 명이 입장해서 네 명씩 두 팀으로 갈라지고, 두 팀은 끝까지 싸운다. 팀원이 모두 먼저 쓰러진 팀이 진다.

서버는 참가자마다 대전 기록을 보관하고, 그 기록으로 실력 점수를 1 이상 1000 이하의 정수로 추정한다. 대전을 최대한 공평하게 맞추려고, 참가자가 접속하면 서버는 실력 점수를 보고 두 팀의 실력 점수 합 차이가 가장 작아지도록 인원을 나눈다.

서버가 이 계산을 제대로 하는지 확인하려고 한다. 참가자의 실력 점수가 주어질 때, 두 팀의 실력 점수 합 차이의 최솟값을 구하라. 두 팀의 인원수는 항상 같아야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 줄이 주어진다. 각 줄은 입장한 참가자 수 $N$으로 시작하고, 그 줄의 나머지 $N$개 정수가 참가자의 실력 점수다. 실력 점수는 정해진 순서 없이 주어진다.

제한

• $1 \le T \le 100$
• $N$은 짝수이고 $2 \le N \le 16$
• 실력 점수는 1 이상 1000 이하의 정수

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 A팀의 실력 점수 합과 B팀의 실력 점수 합의 차이 중 가장 작은 값이다.