该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

传说某一位国王喜欢吃饼干，不过他有一个奇怪的癖好，吃饼干的时候对于饼干的样貌口味以及存在的方式极其苛刻。他所吃的饼干都是通过御用厨师烘焙而成的拥有正反两面的饼干。据说将两块饼干正面和反面合在一起吃下去后会有独特的体验。所以国王随机的将 $n$ 块饼干水平的摆成一条直线。因为是随机摆放，因此这一行饼干会有正面也会有反面。而他只会以正面朝上的饼干开始选择，再匹配一块位于这块饼干的后面反面朝上的饼干，最后一并吃下。但是国王表示“可供我选择的组合太少了，应该让我多一些选择”。于是国王下达一条命令，在摆放完成后可以选择一块饼干让他翻转过来。请聪明的OIer帮助国王让他拥有最多的选择吧。

输入格式

第一行输入一个整数 $t$ 代表接下来有 $t$ 组询问。

接下来的 $t$ 组询问，每组 $2$ 行输入，每组的第一行输入一个整数 $n$ 代表有 $n$ 块饼干，第二行有 $n$ 个被空格分隔开的 $1$ 或 $0$ (这里我们用 $1$ 表示正面朝上的饼干，用 $0$ 表示反面朝上的饼干)。

输出格式

输出 $t$ 行，每行输出一个整数表示该次询问中可以拥有的最大组合数。

样例

输入1

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

输出1

3
7
1
13
2

提示说明

对于第一组样例可以选择把最后一个 $1$ 变为 $0$ ，这样在位置上就会有 $(1,2),(1,3),(1,4)$ 这三种选择。

对于 $100\%$ 的数据，$1\le t \le 10^{4}$，$1 \le n \le 2\cdot 10^{5},\sum n\le 2 * 10^5$。