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$.
