问题描述
zxa有一个集合$A=\{a_1,a_2,\cdots,a_n\}$，$n$表示集合$A$的元素个数，这个集合明显有$(2^n-1)$个非空子集合。
对于每个属于$A$的子集合$B=\{b_1,b_2,\cdots,b_m\}(1\leq m\leq n)$，$m$表示集合$B$的元素个数，zxa定义它的价值是$\min(b_1,b_2,\cdots,b_m)$。
zxa很好奇，如果令$S_{odd}$表示集合$A$的所有含奇数个元素的非空子集合的价值之和，$S_{even}$表示集合$A$的所有含偶数个元素的非空子集合的价值之和，那么$|S_{odd}-S_{even}|$是多少，你能帮助他吗？
输入描述
第一行有一个正整数$T$，表示有$T$组数据。
对于每组数据：
第一行有一个正整数$n$，表示集合有$n$个元素。
第二行有$n$个互异的正整数，表示集合的元素$a_1,a_2,\cdots,a_n$。
每一行相邻数字之间只有一个空格。
$1\leq T\leq 100,1\leq n\leq 30,1\leq a_i\leq 10^9$
输出描述
对于每组数据，输出一行，包含一个非负整数，表示$|S_{odd}-S_{even}|$的值。
输入样例
3
1
10
3
1 2 3
4
1 2 3 4
输出样例
10
3
4
Hint
对于第一组样例，$A=\{10\}$，它只有一个含奇数个元素的子集合$\{10\}$，没有含偶数个元素的子集合，所以$S_{odd}=10,S_{even}=0,|S_{odd}-S_{even}|=10$。
对于第二组样例，$A=\{1,2,3\}$，它有四个含奇数个元素的子集合$\{1\},\{2\},\{3\},\{1,2,3\}$，有三个含偶数个元素的子集合$\{1,2\},\{2,3\},\{1,3\}$，所以$S_{odd}=1+2+3+1=7,S_{even}=1+2+1=4,|S_{odd}-S_{even}|=3$。
