zxa and set

题目链接：

http://acm.hust.edu.cn/vjudge/contest/121332#problem/G

Description

zxa has a set , which has elements and obviously non-empty subsets.

For each subset of , which has elements, zxa defined its value as .

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

Input

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

For each test case:

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

The second line contains distinct positive integers, repersent the elements .

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

Output

For each test case, output in one line a non-negative integer, repersent the value of .

Sample Input

3

1

10

3

1 2 3

4

1 2 3 4

Sample Output

10

3

4

Hint

题意：

给出集合A，B是A的任意子集；某个集合的权值定义为集合元素的最小值；

S-odd为元素个数为奇数的B的个数；

S-even为元素个数为偶数的B的个数；

求abs(S-odd - S-even)；

题解：

看上去好像很麻烦，要算很多次；

尝试把每个元素在结果中出现的次数写成组合数的形式；

再按题意加起来，运用组合数相关公式可以很容易得到：

结果即为A中的最大值；

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define mid(a,b) ((a+b)>>1)

#define LL long long

#define maxn 600000

#define IN freopen("in.txt","r",stdin);

using namespace std;

int n;

int main(int argc, char const *argv[])

{

    //IN;

    int t;cin>>t;

    while(t--)

    {

        scanf("%d",&n);

        int ans = -1;

        while(n--){

            int x;

            cin >> x;

            ans = max(ans, x);

        }

        printf("%d\n", ans);

    }

    return 0;

}