CF2061A Kevin and Arithmetic

为了训练小 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 完成