Chia kẹo cho anh em

Hai anh em được cô chú tặng nhiều gói kẹo và muốn chia thành hai phần sao cho số kẹo ở hai phần chênh nhau ít nhất có thể. Các gói kẹo phải được giữ nguyên, không được bóc ra.

Có \(N\) gói kẹo, gói thứ \(i\) có \(A_i\) viên. Hãy chia toàn bộ các gói vào hai phần (một phần có thể rỗng) sao cho hiệu tuyệt đối giữa tổng số viên kẹo hai phần là nhỏ nhất, và in ra hiệu đó.

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng: dòng đầu chứa \(N\); dòng sau chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

Với mỗi bộ dữ liệu, in ra một dòng chứa hiệu tuyệt đối nhỏ nhất.

Constraints

• \(1 \le T \le 20\)
• \(1 \le N \le 100\)
• \(1 \le A_i \le 500\)

Sample Input

2
5
3 9 4 4 8
3
10 10 7

Sample Output

2
7

Explanation

Bộ 1: tổng số kẹo là \(28\), nếu chia đều mỗi bên phải là \(14\) nhưng không có tập gói nào có tổng \(14\). Chia \(\{9,4\}\) (\(13\)) và \(\{3,4,8\}\) (\(15\)) cho hiệu \(2\), đây là nhỏ nhất. Bộ 2: chia \(\{10,7\}\) (\(17\)) và \(\{10\}\) (\(10\)) cho hiệu \(7\), là nhỏ nhất.