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?
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$
For each test case, output in one line a non-negative integer, repersent the value of $|S_{odd}-S_{even}|$.