No submission language available for this problem.

Background

Special for beginners, ^_^

Description

$bob$ 和 $alice$ 现在有一堆银币，每枚银币价值各不相同，现在想知道他们两各取完这堆银币之后，两人的银币总价值之差的最小值是多少?

ps：一枚硬币不可再切割平分。

Format

Input

数据为多组数据，

第一行一个整数 $T$，表示共有 $T$ 组数据。

每组数据共两行，

第一行一个整数 $n$，代表 $n$ 枚银币。

第二行 $n$ 个整数 $c_i$，代表每枚银币的价值，之间用一个空格间隔。

Output

输出一个整数，代表他们俩均分这堆银币后，相差的价值最小。

Samples

1
3
2 3 5

1
4
1 2 4 6

0

1

Limitation

【数据规模与约定】

$n\leq 100, 1\leq c_i\leq 500$。