You are given an array $$$a$$$ of $$$n$$$ integers. Alice and Bob will play a game with this array.

Before the game with Bob starts, Alice can increment any element of the array any number of times, each increment taking one move. One increment consists of a single addition by $$$1$$$ to one index.

After that, the game starts and Bob and Alice take turns, with Bob making the first move. On Bob's turn, he can choose any two indices $$$i$$$ and $$$j$$$ and swap the array elements at these indices (note that Bob may choose $$$i = j$$$, in which case the array remains unchanged after the swap).

On Alice's turn, if $$$a_1$$$ is even, she finds the largest $$$j \leq |a|$$$ such that $$$a_i$$$ is even for all $$$i \leq j,$$$ then sets $$$a_i := a_i/2$$$ for $$$i \leq j.$$$ Otherwise she sets $$$a_1 := a_1 - 1.$$$ If any element becomes zero, it automatically gets erased from the array (and the other elements are re-indexed accordingly).

The game ends when the array is empty.

Alice wants to minimize the number of moves she makes, while Bob wants to maximize the number of moves Alice makes. Note that the number of moves is the sum of the number of initial additions and the number of turns Alice plays after.

How many moves will Alice make with optimal play?

Input

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

The first line of each test case contains a single integer $$$n \, (1 \le n \le 10^5)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_{n}\,(1 \le a_i \le 10^5)$$$ — the elements of the array.

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

Output

For each test case, output a single integer — the number of moves Alice will make if both players play optimally.

Note

In the first case, Alice chooses not to add to any element initially. On the first move, Bob chooses $$$i = j = 1$$$ (not swapping any elements). Then Alice subtracts $$$1$$$ from $$$a_1,$$$ making the array $$$[2,3]$$$. Next, Bob again chooses $$$i = j = 1.$$$ Alice divides $$$a_1$$$ by $$$2$$$, and the array becomes $$$[1,3]$$$. Bob again chooses $$$i = j = 1.$$$ Alice subtracts from $$$a_1,$$$ and the array becomes $$$[3]$$$. Bob must now choose $$$i = j = 1,$$$ and Alice takes $$$3$$$ more moves to make the array empty. In total, Alice takes $$$6$$$ moves. It can be shown that this is the result of optimal play.

In the second test case, Alice again chooses not to add to any element initially. It can be shown that with optimal play, Alice takes $$$5$$$ moves.

diss_quack and Array Game

Examples