No testdata at current.

目描述

在浙江师范大学 ACM 集训队，队员平时集训脑力劳动力比较重。为了劳逸结合，我们敬爱的韩老师准备了一场拔河比赛，让队员放松心情。

为了拔河比赛的公正性，韩老师提出以下要求： . 拔河比赛两边人数最多不能相差1 。 . 每个队员都有体重，我们要使两边比赛的人体重和相差最小。

现在有N 个队员，韩老师想你帮忙分配，并且把分配后两边体重和之差最小值输出。

输入格式

首先输入T ，表示有 T 组样例。

每个样例：

首先输入人数 N，占一行。

后面跟着 N个数，表示N 个人的体重W1-WN 。

输出格式

对于每个样例输出一行，一个整数表示两边体重之差的绝对值。

样例

输入样例复制

1
3
55 50 100

输出样例复制

5

数据范围与提示