You are given an array of $$$n$$$ non-negative integers.

You want to answer given $$$q$$$ independent scenarios. In the $$$i$$$-th scenario, you are allowed to perform the following operation at most $$$b_i$$$ times:

Choose an element of the array and increase it by $$$1$$$.

Your goal is to maximize the number of bits that are equal to $$$1$$$ in the bitwise OR of all numbers in the array. Find this number for each scenario.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^{5}$$$) — the size of the array and the number of scenarios.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{9}$$$) — the elements of the array.

The $$$i$$$-th of the next $$$q$$$ lines contains a single integer $$$b_i$$$ ($$$0 \leq b_i \leq 10^{9}$$$) — the maximum number of operations allowed in the $$$i$$$-th scenario.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$10^{5}$$$.

Output

For each test case, output $$$q$$$ lines, the $$$i$$$-th of them containing a single integer — the maximum possible number of bits equal to $$$1$$$ in the bitwise OR in the $$$i$$$-th scenario.

Note

Visualizer link

In the first test case:

In the first scenario, we don't have any operations, and therefore the answer is equal to the number of $$$1$$$-bits in the bitwise OR of the original array, $$$0$$$, which has $$$0$$$ bits set in its binary representation.
In the second scenario, one way of achieving $$$1$$$ bit set in the bitwise OR is increasing $$$a_1$$$ by $$$1$$$ twice, obtaining a bitwise OR of $$$2={(10)}_2$$$. It can be shown that it is the best possible value we can obtain by performing the operation at most twice.
In the third scenario, one way of achieving a result of $$$2$$$ is adding $$$1$$$ to $$$a_1$$$ three times, which can be shown to be optimal. Note that you don't have to apply the operation $$$4$$$ times.

In the second test case:

In the first scenario, we don't have any operations, and therefore the answer is equal to the number of $$$1$$$-bits in the bitwise OR of the original array, which is $$$2$$$.
In the second scenario, one way of achieving a result of $$$3$$$ is adding $$$1$$$ to $$$a_2$$$ three times, which can be shown to be optimal.

Maximum OR Popcount

Examples