解题思路

先只看一次操作对数组元素和的奇偶性有什么影响。

设当前数组元素和为 $S$。

两种操作分别是：

• 删除一个元素

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}。你可以进行若干次操作，每次操作从下列两种中任选其一：

• 选择一个元素将其删除，剩余元素按照原顺序拼接；

• 选择一个元素将其增加 $1$ 或者减少 $1$ 。

要求：每次操作完成后，数组所有元素的和必须是 $2$ 的倍数(即为偶数)。请你输出最多可以进行多少次操作。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1≤t≤10^4)$ 表示数据组数，每组测试数据描述如下：

第一行输入一个整数 $n(1≤n≤2×10^5)$；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$ 表示数组 $a$ 。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出一个整数，表示最多可以进行的操作次数。

样例1

输入

2
5
1 2 3 4 5
4
2 2 1 1

输出

4
2

说明

(对应第一组)：

• 初始元素和为奇数，可以先对某个奇数元素执行一次 $±1$ ，使总和变为偶数;

• 此后总和为偶数，只能删除偶数元素，直至无法继续;共可操作 $4$ 次。