Ravi gives a challenge to Rupali to find the sum of elements of a power set ( the sum of elements of a set is sum of its all integer elements ,say ).

 For example :
    Set ={ 5, 9}
    Power Set={ {5}, {9}, {5,9} }              ( empty set is not considered in it )
    Then sum of this is (5) + (9) + (5+9) = 28

Meanwhile, Ravi gone for the shopping and Rupali need your help to win this challenge before Ravi comes back.

Input Format:

First line contains an integer denoting the number of Test Cases T .

For each test case two lines are specified ,first line contain number N denoting number of elements in a set and next line contain N space separated integers denoting the elements of set.

Output Format:

For T test cases ,T line will output where each line contain the sum.

Constraints:

1<=T<=100

1<=N<=1000