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\).