Problem Statement

There are $N$ bags numbered $1,2,\dots,N$. Also, for each $i=0,1,\dots,M-1$, there are $A_i$ packages of weight $2^i$. There are $A_0+A_1+\dots+A_{M-1}$ packages in total.

Every package is put into exactly one of the bags. Some bags may remain empty.

For each bag, the sum of the weights of all packages in that bag is called the weight of the bag.

Find the minimum possible value of the maximum of the weights of the $N$ bags.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 10^5$
• $1 \le N \le 10^6$
• $1 \le M \le 40$
• $0 \le A_i \le 10^6$
• The sum of $M$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N M
A_0 A_1 \ldots A_{M-1}

Output

Output $T$ lines.

The $i$-th line should contain the minimum possible value of the maximum of the weights of the bags for the $i$-th test case.