题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2...a_n$。

现有 $1$ 次操作的机会，可以选择其中一个数字 $+1$。

操作最多 $1$ 次（也可以不操作），询问最后包含偶数的连续子段的最大数量。

输入格式

第一行，$1$ 个正整数 $t$，表示数据的组数。

接下来 $2\times t$ 行，表示每组数据。

其中第一行为 $n$，表示当前该组数据元素个数。

第二行为 $n$ 个数字，分别为 $a_i$。

输出格式

$t$ 行，对每组数据表示最多操作一次之后的包含偶数的连续子段最大数量。

输入输出样例

1
4
2 1 3 4

9

样例 $\tt \#1$说明

• 操作数为 $0$ 时，有 $[2],[2,1],[2,1,3],[2,1,3,4],[1,3,4],[3,4],[4],7$ 个子段。
• 执行 $1$ 次操作之后，将原始的 $a_2=1$ 改为 $a_2=2$，原数组变为 $[2,2,3,4]$，其中包含偶数的子段有 $[2],[2,2],[2,2,3],[2,2,3,4],[2],[2,3],[2,3,4],[3,4],[4]$ 此时结果更大，为 $9$。

数据范围

• 对于 $30\%$ 的数据，$1\le t,n\le 100$
• 对于 $100\%$ 的数据，$1\le t\le 10^3,1\le n\le 2\times 10^5,0\le a_i\le 10^9,\sum_n\le 2\times10^5$