쿠키

Hektor와 Zbyszek은 매일 아침 쿠키를 사러 갑니다. 제빵사는 매번 쿠키 $N$개를 준비하며, 각 쿠키에는 그 품질을 나타내는 자연수 하나가 붙어 있습니다. 두 사람은 번갈아 쿠키를 한 개씩 고르는데, 언제나 남아 있는 쿠키 중 품질이 가장 좋은 것을 집습니다.

이번 주에는 Zbyszek이 먼저 고를 차례인데, Hektor는 이것이 매우 불공평하다고 생각합니다. Hektor는 Zbyszek의 우위, 즉 (Zbyszek이 고른 쿠키들의 품질 합)에서 (Hektor가 고른 쿠키들의 품질 합)을 뺀 값을 가능한 한 작게 만들고 싶어 합니다. 이를 위해 그는 작은 속임수를 쓰기로 합니다.

Hektor는 이른 아침, 일을 마치려는 제빵사에게 전화를 걸어 오늘 준비한 쿠키에 대해 물었습니다. 제빵사는 Hektor를 무척 아끼기에, 그의 부탁을 들어 Hektor가 원하는 품질의 쿠키 한 개를 이 묶음에 더 넣어 줄 수 있습니다.

준비된 쿠키들의 품질이 주어지고 임의의 자연수 품질을 가진 쿠키를 최대 한 개까지 추가할 수 있을 때, Zbyszek이 Hektor보다 앞서는 우위의 최솟값을 구하세요.

입력의 첫 줄에는 테스트 케이스의 개수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 $Z$개의 테스트 케이스가 차례로 주어집니다.

각 테스트 케이스는 제빵사가 준비한 쿠키의 개수를 나타내는 자연수 $N$ ($1 \le N \le 1\,000\,000$)으로 시작합니다.

다음 줄에는 각 쿠키의 품질을 나타내는 $N$개의 자연수 $A_i$ ($1 \le A_i \le 1000$)가 주어집니다.

각 테스트 케이스마다, Zbyszek이 고른 쿠키들의 품질 합과 Hektor가 고른 쿠키들의 품질 합의 차이의 최솟값을 한 줄에 하나씩 출력하세요.