题目描述

如果一个数组 $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$。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $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$ 的总和没有上界。

输出格式

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

说明/提示

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

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

在第三个测试用例中，如果对下标 $1$ 执行一次操作，$a$ 变为 $[0,2,4]$。由于 $[0,2,4]$ 是好的，所以答案是 $1$。

在第四个测试用例中，需要对下标 $1$ 执行四次操作。所有操作后，$a$ 变为 $[0]$。可以证明，不可能用更少的操作次数使 $a$ 变为好的。

由 ChatGPT 4.1 翻译

样例

4
4
1 1 1 1
2
7 4
3
1 2 4
1
15

0
2
1
4