zxa and set

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

zxa has a set $A=\{a_1,a_2,\cdots,a_n\}$, which has $n$ elements and obviously $(2^n-1)$ non-empty subsets.

For each subset $B=\{b_1,b_2,\cdots,b_m\}(1\leq m\leq n)$ of $A$, which has $m$ elements, zxa defined its value as $\min(b_1,b_2,\cdots,b_m)$.

zxa is interested to know, assuming that $S_{odd}$ represents the sum of the values of the non-empty sets, in which each set $B$ is a subset of $A$ and the number of elements in $B$ is odd, and $S_{even}$ represents the sum of the values of the non-empty sets, in which each set $B$ is a subset of $A$ and the number of elements in $B$ is even, then what is the value of $|S_{odd}-S_{even}|$, can you help him?

Input

The first line contains an positive integer $T$, represents there are $T$ test cases.

For each test case:

The first line contains an positive integer $n$, represents the number of the set $A$ is $n$.

The second line contains $n$ distinct positive integers, repersent the elements $a_1,a_2,\cdots,a_n$.

There is a blank between each integer with no other extra space in one line.

$1\leq T\leq 100,1\leq n\leq 30,1\leq a_i\leq 10^9$

Output

For each test case, output in one line a non-negative integer, repersent the value of $|S_{odd}-S_{even}|$.

Sample Input

3 1 10 3 1 2 3 4 1 2 3 4

Sample Output

10 3 4
Hint
For the first sample, $A=\{10\}$, which contains one subset $\{10\}$ in which the number of elements is odd, and no subset in which the number of elements is even, therefore $S_{odd}=10,S_{even}=0,|S_{odd}-S_{even}|=10$. For the second sample, $A=\{1,2,3\}$, which contains four subsets $\{1\},\{2\},\{3\},\{1,2,3\}$ in which the number of elements is odd, and three subsets $\{1,2\},\{2,3\},\{1,3\}$ in which the number of elements is even, therefore $S_{odd}=1+2+3+1=7,S_{even}=1+2+1=4,|S_{odd}-S_{even}|=3$.

Hint

wange2014

Source

BestCoder Round #83

提交代码