如果 $$$b$$$ 的元素总和是偶数,则数组 $$$b$$$ 是好的。
给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。在一次操作中,您可以选择索引 $$$i$$$ 并更改 $$$a_i := \lfloor \frac{a_i}{2} \rfloor$$$。 $$$^\匕首$$$
找出使 $$$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$$$ 良好所需的最少操作数。
示例
输入 #1
4 4 1 1 1 1 2 7 4 3 1 2 4 1 15
输出 #1
0 2 1 4
注意
在第一个测试用例中,数组 $$$a$$$ 已经很好了。
在第二个测试用例中,我们可以对索引 $$$2$$$ 执行两次。第一次操作后,数组 $$$a$$$ 变为 $$$[7,2]$$$。再次对索引 $$$2$$$ 执行后,$$$a$$$ 变为 $$$[7,1]$$$,这很好。可以证明,不可能用较少的操作次数就使 $$$a$$$ 变得很好。
在第三个测试用例中,如果我们对索引 $$$1$$$ 执行一次操作,则 $$$a$$$ 变为 $$$[0,2,4]$$$ 。由于 $$$[0,2,4]$$$ 很好,答案是 $$$1$$$。
在第四个测试用例中,我们需要对索引 $$$1$$$ 执行四次操作。完成所有操作后,$$$a$$$ 变为$$$[0]$$$。可以证明,不可能用较少的操作次数就使 $$$a$$$ 变得很好。