说明

给定一个长 $n$ 的非负整数序列 $a$，你可以进行如下形式的操作任意次：

1. 选择一个区间 $[l,r]$（$l$ 和 $r$ 可以相等）；
2. 令 $s=\sum \limits_{i\in [l,r]} a_i$，令 $k$ 为最大的非负整数使得 $2^k\le s$（若 $s=0$ 则 $k=0$）；
3. 获得 $k$ 个金币，并将 $a_{[l,r]}$ 删去。之后 $a_{[1,l-1]}$ 和 $a_{[r+1,n]}$ 会拼接起来，即新的 $a$ 长度为 $n-r+l-1$；

求最多能获得多少个金币。

输入格式

第一行两个整数 $c,T$ 分别表示测试点所属的子任务编号（样例保证 $c=0$）和数据组数。

对于每组数据，输入两行：

• 第一行一个整数 $n$；

• 第二行 $n$ 个整数表示序列 $a$；

输出格式

对于每组数据，输出一行一个整数表示答案。

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

提示

【样例 1 解释】

第一次操作：选择区间 $[2,2]$，此时 $s=2,k=1$，获得 $1$ 金币，操作后序列变为 3 1 1 4；

第二次操作：选择区间 $[1,3]$，此时 $s=5,k=2$，获得 $2$ 金币，操作后序列变为 4；

第三次操作：选择区间 $[1,1]$，此时 $s=4,k=2$，获得 $2$ 金币，操作后序列变为空序列；

总共获得 $5$ 金币，可以证明这是能获得的最多金币数。

【数据范围】

对于所有测试数据，$1\le n,\sum n\le 10^6$，$0\le a_i\le 10^{18}$，$1\le T\le 100$。