### Subsets

Chef is given an array of length n. Help him to print the sum of all subsets of the array.

Total sum = sum of subset1 + sum of subset2 +… + sum of subsetk

Solve the problem using recursion.

### Input format

First line contains integer t, number of testcases. For each testcase : First line contains an integer denoting the value of n Second line contains n space-separated integers.

### Output format

For each testcase, print the sum of all subsets.

### Constraints

1<=t<=10, 1<=n<=10, 1<=a[i]<=105

### Example

#### Input

1 8 2 4 1 3 6 3 2 6

#### Output

3456

and please explain if i guess similar type of problem,how to think and why recursion is use and why for loop is used. we need to do this using brute force and recursion.