AT_arc219_f.Range Division

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.

给你一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$。

你可以对 $A$ 执行零次或多次如下操作。每次操作按顺序执行以下步骤：

• 选择一对满足以下所有条件的整数 $(l,r)$：
  • $1\le l\le r\le N$
  • $A_l,A_{l+1},\ldots,A_r$ 具有相同的奇偶性（即全为偶数或全为奇数）。
• 对每个 $k=l,l+1,\ldots,r$，将 $A_k$ 替换为 $\displaystyle\left\lfloor\frac{A_k}2 \right\rfloor$。

求使 $A$ 的所有元素均变为 $0$ 所需的最少操作次数。

你将得到 $T$ 组测试数据；请分别求解每组数据。

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$

输入从标准输入中按以下格式给出：

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

每个测试用例按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

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

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
Consider the first test case.

By performing operations as follows, all elements of $A$ can be made $0$ in five operations:

• Choose $(l,r)=(1,1)$. $A$ becomes $(4,12)$.
• Choose $(l,r)=(1,2)$. $A$ becomes $(2,6)$.
• Choose $(l,r)=(1,2)$. $A$ becomes $(1,3)$.
• Choose $(l,r)=(1,2)$. $A$ becomes $(0,1)$.
• Choose $(l,r)=(2,2)$. $A$ becomes $(0,0)$.

It is impossible to make all elements of $A$ equal to $0$ in fewer than five operations, so output $5$.

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.

样例 1 解释：
考虑第一个测试用例。

通过执行如下操作，可在五次操作内将数组 $A$ 的所有元素变为 $0$：

• 选择 $(l,r)=(1,1)$，此时 $A$ 变为 $(4,12)$。
• 选择 $(l,r)=(1,2)$，此时 $A$ 变为 $(2,6)$。
• 选择 $(l,r)=(1,2)$，此时 $A$ 变为 $(1,3)$。
• 选择 $(l,r)=(1,2)$，此时 $A$ 变为 $(0,1)$。
• 选择 $(l,r)=(2,2)$，此时 $A$ 变为 $(0,0)$。

无法用少于五次操作使 $A$ 的所有元素变为 $0$，因此输出 $5$。

限制条件

• $1\le T$
• $1\le N\le 30$
• $0\le A_i< 2^{60}$
• 所有测试用例的 $N$ 之和不超过 $30$。
• 所有输入值均为整数。