Problem Description

You are given a non-negative integer sequence $a$ of length $n$. You may perform the following operation any number of times:

1. Choose an interval $[l,r]$ (where $l$ and $r$ may be equal).
2. Let $s=\sum \limits_{i\in [l,r]} a_i$, and let $k$ be the largest non-negative integer such that $2^k\le s$ (if $s=0$ then $k=0$).
3. You gain $k$ coins, and delete $a_{[l,r]}$. After that, $a_{[1,l-1]}$ and $a_{[r+1,n]}$ are concatenated, i.e., the new length of $a$ becomes $n-r+l-1$.

Find the maximum number of coins you can obtain.

Input Format

The first line contains two integers $c,T$, representing the subtask ID of the test point (the samples guarantee $c=0$) and the number of test cases.

For each test case, the input contains two lines:

• The first line contains an integer $n$.
• The second line contains $n$ integers representing the sequence $a$.

Output Format

For each test case, output one line with one integer representing the answer.

0 1
5
3 2 1 1 4

5

0 1
12
1 0 3 2 2 1 4 5 6 8 7 9

19

Hint

Sample 1 Explanation

First operation: choose interval $[2,2]$. Then $s=2,k=1$, you gain $1$ coin, and the sequence becomes 3 1 1 4 after the operation.

Second operation: choose interval $[1,3]$. Then $s=5,k=2$, you gain $2$ coins, and the sequence becomes 4 after the operation.

Third operation: choose interval $[1,1]$. Then $s=4,k=2$, you gain $2$ coins, and the sequence becomes an empty sequence after the operation.

In total you gain $5$ coins. It can be proven that this is the maximum number of coins that can be obtained.

Constraints

For all testdata, $1\le n,\sum n\le 10^6$, $0\le a_i\le 10^{18}$, $1\le T\le 100$.

Translated by ChatGPT 5