题目描述

给定一个长为 $n$ 的序列 $\{a_i\}$，定义一个序列的优美度为包含至少一个偶数的子段的个数。你可以将序列中至多一个元素增加 $1$，你想知道这个序列最大可以达到的优美度。

例如：$[1,2,3]$ 的优美度是 $4$，对 $1$ 或 $3$ 进行操作都可以使得新序列的优美度变为 $5$，即为答案。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行一个正整数 $n$，代表序列长度；
• 接下来一行 $n$ 个整数，代表序列 $[a_1,a_2,\ldots,a_n]$。

输出格式

对于每组数据，输出一行一个整数，代表最大可以达到的优美度。

3
3
1 2 3
3
0 1 1
6
1 1 4 5 1 4

5
5
17

数据范围

• 对于 $30\%$ 的数据，$T \le 10$，$n \le 10^3$；
• 对于另外 $30\%$ 的数据，存在一个 $1 \le k \le n$，使得 $a_1,\ldots,a_k$ 是偶数，$a_{k+1},\ldots,a_n$ 是奇数；
• 对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n, \sum n \le 2 \cdot 10^5$，$0 \le a_i \le 10^9$。