No testdata at current.

[T2] 子段

题目描述

给定一个长为 $n$ 的序列 $a_1,a_2,\dots,a_n$，定义这个序列的优美度为：其中包含至少一个偶数的子段个数。

你可以将这个序列中至多一个元素增加 $1$。请你求出，在最优操作后，这个序列的优美度最大可以达到多少。

输入格式

从标准输入按以下格式读取数据：

$T$

$n$

$a_1$ $a_2$ $\dots$ $a_n$

其中：

• 第一行输入一个正整数 $T$，表示数据组数。
• 对于每组数据：
  • 第一行输入一个正整数 $n$；
  • 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

对于每组数据，输出一行一个整数，表示最大可能的优美度。

数据范围

根据公开检索片段可确认：

• $1 \le T \le 10^5$
• $1 \le n$
• 所有测试数据中 $\sum n \le 2 \times 10^5$
• $0 \le a_i \le 10^9$

样例

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

5
5
17