该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

某学校的小盆友们参加了一个健身减肥活动，现在需要制定一个锻炼计划。需要分成两组，为了保证公平，需要两组的人数至多差1人，除了锻炼的小朋友之外，还要安排至少一个小朋友作为拉拉队员在旁边加油打气

给定一组小盆友的体重，希望你能帮忙找到一个锻炼计划，使得每组的小盆友的初始体重之和差异尽量小。

输入格式

第一行一个整数T，表示数据的组数。

每组数据，第一行一个整数n，表示班里小盆友的个数。

每组数据，第二行n个整数，表示每个小盆友的体重。

输出格式

输出T个整数，表示最小的两组的各自体重之和的差异。

样例

输入：

2
3
30 31 100
4
30 38 67 1

输出：

1
1

数据范围与提示

对于100%的数据，3≤n≤15，小盆友的体重范围在[30, 10000]之间, 1 <= T <= 10, 对于单组数据，至多只存在一个 n > 10。

样例