CF1762A.Divide and Conquer

An array $b$ is good if the sum of elements of $b$ is even.

You are given an array $a$ consisting of $n$ positive integers. In one operation, you can select an index $i$ and change $a_i := \lfloor \frac{a_i}{2} \rfloor$. $^\dagger$

Find the minimum number of operations (possibly $0$) needed to make $a$ good. It can be proven that it is always possible to make $a$ good.

$^\dagger$ $\lfloor x \rfloor$ denotes the floor function — the largest integer less than or equal to $x$. For example, $\lfloor 2.7 \rfloor = 2$, $\lfloor \pi \rfloor = 3$ and $\lfloor 5 \rfloor =5$.

若数组 $b$ 的元素之和为偶数，则称 $b$ 是“好”的。

给定一个由 $n$ 个正整数构成的数组 $a$。在一次操作中，你可以选择一个下标 $i$，并将 $a_i$ 修改为 $\lfloor \frac{a_i}{2} \rfloor$。$^\dagger$

求使 $a$ 变为“好”的数组所需的最少操作次数（可以为 $0$）。可以证明：总能通过若干次操作使 $a$ 变为“好”的数组。

$^\dagger$ $\lfloor x \rfloor$ 表示向下取整函数——即不超过 $x$ 的最大整数。例如，$\lfloor 2.7 \rfloor = 2$，$\lfloor \pi \rfloor = 3$，$\lfloor 5 \rfloor = 5$。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 50$) — the length of the array $a$.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^6$) — representing the array $a$.

Do note that the sum of $n$ over all test cases is not bounded.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 50$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 10^6$），表示数组 $a$。

请注意，所有测试用例的 $n$ 之和没有上界。

For each test case, output the minimum number of operations needed to make $a$ good.

对于每个测试用例，输出使 $a$ 变为“好”的数组所需的最少操作次数。

In the first test case, array $a$ is already good.

In the second test case, we can perform on index $2$ twice. After the first operation, array $a$ becomes $[7,2]$. After performing on index $2$ again, $a$ becomes $[7,1]$, which is good. It can be proved that it is not possible to make $a$ good in less number of operations.

In the third test case, $a$ becomes $[0,2,4]$ if we perform the operation on index $1$ once. As $[0,2,4]$ is good, answer is $1$.

In the fourth test case, we need to perform the operation on index $1$ four times. After all operations, $a$ becomes $[0]$. It can be proved that it is not possible to make $a$ good in less number of operations.

在第一个测试用例中，数组 $a$ 已经是“好”的。

在第二个测试用例中，我们可以在下标 $2$ 处执行操作两次。第一次操作后，数组 $a$ 变为 $[7,2]$；再次对下标 $2$ 执行操作后，$a$ 变为 $[7,1]$，此时它是“好”的。可以证明，无法用少于两次的操作使 $a$ 变为“好”的。

在第三个测试用例中，若对下标 $1$ 执行一次操作，则 $a$ 变为 $[0,2,4]$。由于 $[0,2,4]$ 是“好”的，因此答案为 $1$。

在第四个测试用例中，我们需要对下标 $1$ 执行四次操作。所有操作完成后，$a$ 变为 $[0]$。可以证明，无法用少于四次的操作使 $a$ 变为“好”的。