Problem Statement

You are given a sequence of non-negative integers $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

You can perform the following operation on $A$ zero or more times. In one operation, perform the following steps in order:

• Choose a pair of integers $(l,r)$ satisfying all of the following conditions:
• $1\le l\le r\le N$
  • $A_l,A_{l+1},\ldots,A_r$ all have the same parity (that is, they are all even or all odd).
• For each $k=l,l+1,\ldots,r$, replace $A_k$ with $\displaystyle\left\lfloor\frac{A_k}2 \right\rfloor$.

Find the minimum number of operations needed to make all elements of $A$ equal to $0$.

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

Constraints

• $1\le T$
• $1\le N\le 30$
• $0\le A_i< 2^{60}$
• The sum of $N$ over all test cases is at most $30$.
• 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
A_1 A_2 \ldots A_N

Output

Output the answers for the test cases in order, separated by newlines.