"Now winter is truly coming. In the winter, we must protect ourselves. Look after one another", John muttered to Sam.

Sam, being a good friend of Jon Snow, has to save humanity from the mighty dead army of Night King. However, in order to save it, he has to collect dragon glasses with maximum capacity placed in a pyramidal building of Dragonstone.

The dragon glasses are placed in that pyramidal building in such a manner that at the top floor, there is 1 dragon glass, second last floor has 2 dragon glasses, third last floor has 2^2(=4) dragon glasses and so on. Each dragon glass has a specific killing capacity(i.e. a dragon glass with 'x' capacity can kill 'x' enemies). Sam has to collect dragon glasses with maximum capacities such that he can't choose dragon glasses of 2 adjacent floors.

Find the maximum number of deads Sam can kill by collecting those dragon glasses with above constraint.

Note: The first(or ground) floor of the building may or may not have dragon glasses in power of 2.

Input format:

There are number of test cases T.

Each test case contains two lines.

First line is the, the number of dragon glasses N and Second line contains N integers separated by space which denotes the killing capacity of each dragon glass arranged in the building in this fashion
1 // top floor
2 3 // 2nd last floor
4 5 6 7 //3rd last floor & so on

Output Format:

For each test case, in new line, print the maximum enemies Sam can Kill .

Constraints:

1 <= T <= 100

1 <= N <= 100000

1 <= capacity <= 1000