You are given an array $a$ consisting of $n$ integers. In one move, you can jump from your current index $i$ to some index $j$ if,

1. $i < j$
2. $j \leq n$
3. $(j - i) = (2 ^ K)$ (where $K \ge 0$) (i.e difference between the current index and next index should be equal to some power of $2$)

You will start from index $1$ and your task is to reach index $n$ maximizing the sum of the path.

Sum of the path:

Let the indices that you go through while going from index $1$ to index $n$ are $1, i_2, i_3, ... , n$. So, sum of the path here is equal to $a[1] + a[i_2] + a[i_3] + ... + a[n]$.

Input Format:

•  The first line contains one integer $T$ $-$ the number of test cases. Then $T$ test cases follow.
• The first line of each test case contains a single integer $n$ $-$ the number of elements in array $a$.
• The second line of each test case contains $n$ integers $-$ the elements of the array $a$.

Output Format:

For each test case, output in a seperate line:

Maximum sum of path if you start from index $1$ and stop at index $n$.

 Constraints:

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^6$
• $-10^9 \leq a_i \leq 10^9$ for all $i$ from $1$ to $n$.
• It is guaranteed that sum of $N$ over all test cases doesn't exceed $10^6$.