Hạo và Huy là hai anh em, hai chú nhóc này rất thích kẹo ngọt. Một hôm Chú của hai nhóc ở Hàn Quốc về mua cho hai nhóc rất nhiều kẹo. Vấn đề bây giờ là chia kẹo ra hai phần để một nhóc một phần. Cả hai nhóc đều muốn chênh lệch số lượng kẹo giữa hai phần ít nhất có thể để phần nhiều dành cho cậu em.

Cho \(N\) gói kẹo, gói thứ \(i\) có \(a_i\) viên. Hãy chia các gói thành \(2\) phần sao cho chênh lệch giữa \(2\) phần là ít nhất. Không được mở các gói kẹo nhé!

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(T\) biểu thị tổng số trường hợp kiểm tra.
• Mỗi trường hợp thử nghiệm gồm hai dòng. Dòng đầu tiên chứa \(N\), biểu thị số bao kẹo và dòng thứ hai chứa số kẹo có trong \(N\) gói kẹo này.

Dữ liệu ra

• Trong mỗi dòng riêng biệt in chênh lệch tuyệt đối tối thiểu

Ràng buộc

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

Input 1

2
4
1 6 5 11
4
36 7 46 40

Output 1

1
23