← 返回题目列表

Codeforces · 2061/A

A. 凯文和算术

中文机器翻译题面 查看原题

为了训练小凯文的算术技能,他的母亲设计了以下问题。

给定 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ 和初始化为 $$$0$$$ 的总和 $$$s$$$,Kevin 按顺序对 $$$i = 1, 2, \ldots, n$$$ 执行以下操作:

- 将 $$$a_i$$$ 添加到 $$$s$$$。如果结果 $$$s$$$ 是偶数,Kevin 就得一分,并反复将 $$$s$$$ 除以 $$$2$$$,直到结果变为奇数。

请注意,凯文每次操作最多可以获得一分,无论他做了多少个分区。

由于这些划分被认为对凯文的发展更有利,因此他的母亲希望重新排列$$$a$$$,以便凯文的总点数最大化。确定最大点数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n \leq 100$$$) — 整数的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i \leq 10^9$$$)。

输出

对于每个测试用例,输出一个整数——最大点数。

示例

输入 #1

5
1
1
2
1 2
3
2 4 6
4
1000000000 999999999 999999998 999999997
10
3 1 4 1 5 9 2 6 5 3

输出 #1

0
2
1
3
8

注意

在第一个测试用例中,$$$a$$$ 的唯一排列是$$$[1]$$$。 $$$s$$$ 变为 $$$1$$$。凯文没有获得任何积分。

在第二个测试用例中,$$$a$$$ 唯一可能的排列是$$$[2, 1]$$$。 $$$s$$$ 依次变为 $$$1$$$ 和 $$$1$$$。凯文在两次行动中都获得了积分。

在第三个测试用例中,$$$a$$$ 的一种可能排列是$$$[2, 4, 6]$$$。 $$$s$$$ 依次变为 $$$1$$$、$$$5$$$ 和 $$$11$$$。凯文在第一次行动中获得一分。