We are given an array of integers of size N;  This array can be visualized as a Quad-Tree (Where each node can have 0 to 4 children in total).

For any index i in the array - If we want to find it's children then formula for finding indices of four children is 4*i+1, 4*i+2, 4*i+3, 4*i+4

For above given array, if we visualize it as a Quad-Tree. Print the Maximum Sum out of all the paths starting from Root and Ending at Leaf.  

In above diagram (quad tree) all the root to leaf paths with their sums are

20 + 4 - 7 = 17
20 + 4 - 8 = 16
20 + 4 + 3 = 27
20 + 4 - 1 = 23
20 - 9 + 20 = 31
20 - 1 = 19
20 + 5 = 25

Max out of all of these is 31.  Hence that is the answer.

INPUT FORMAT
Line 1:  Integer T - Number of test cases.
Each Test Case has one line, Size of Array N followed by array elements
    N a1 a2 a3 ... an

OUTPUT FORMAT
For Each Test Case, print a single integer that represents maximum sum from root to leaf path, if array is visualized as a Quad-Tree.

CONSTRAINTS
1 <= t <= 100
1 <= n <= 3000
-5000 <= a[i] <= 5000