题目描述

为了训练小 Kevin 的算术能力，他的母亲设计了以下问题。

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

• 将 $a_i$ 加到 $s$ 上。若此时 $s$ 为偶数，Kevin 获得 1 分，并不断将 $s$ 除以 $2$ 直到其变为奇数。

注意无论执行多少次除法操作，Kevin 每次操作最多只能获得 1 分。

由于这些除法操作被认为对 Kevin 的发展更有益，他的母亲希望重新排列 $a$ 的顺序，使得 Kevin 获得的总分数最大化。请确定最大可能的分数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 $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$）。

输出格式

对于每个测试用例，输出一个整数——最大可能获得的分数。

说明/提示

第一个测试用例中，$a$ 的唯一排列为 $[1]$。$s$ 变为 $1$，Kevin 未获得分数。

第二个测试用例中，$a$ 的唯一可能排列为 $[2, 1]$。$s$ 依次变为 $1$ 和 $1$，Kevin 在两次操作中均获得分数。

第三个测试用例中，一种可能的排列为 $[2, 4, 6]$。$s$ 依次变为 $1$、$5$ 和 $11$，Kevin 在第一次操作中获得 1 分。

翻译由 DeepSeek R1 完成

样例

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

0
2
1
3
8