Babloo Emilio Escobar Gaviria was an Indian code lord and code trafficker. He wants to smuggle his code coins out of the country, therefore, he needs your help to maximize his profit.

There is only one path for Babloo to escape the country which is filled with either code coin treasures (represented as a number greater than 0 which will be the amount of code coin present in that treasure) or corrupt policemen (represented as a 0). While leaving the country Babloo has to pass through all of the code coin treasures and policemen, and he can collect any amount of code coin (possibly 0) if he passes through the treasure but whenever he come across a policeman he has to give half of his code coins from his current inventory (to make the coins integer, take the floor function for half of the coins).

Now Babloo considers his profit = amount of code coin left at the end - the total amount of code coin given to the policemen. Your task is to help Babloo maximize the profit

Input:

The first line contains T ,the number of test cases. The first line of each test case consists of an integer L, the length of the path that Babloo has to take in order to escape the country, which is followed by L integers (X₁ to X_L), each representing either the corrupt policeman or the amount the code coins present in that treasure.

Output:

Print a single integer representing maximum profit that Babloo can achieve

Constraints:

$1 <= T <= 10$
$1 <= L <= 1000$
$0 <= X$_i $<= 1000$