题目描述

Bob 最近正在学习二进制，但二进制的每一位上只能是 $0$ 或 $1$，这让 Bob 觉得很无趣，于是他研究出了一种新的二进制：每一位上只能是 $-1$ 或 $1$！

Bob 想研究的新二进制数有 $n$ 位，它可以表示为 $b_1\times 2^0+b_2\times 2^1+\cdots+b_n\times 2^{n-1}$，其中 $b_i$ 等于 $\pm1$。进一步地，Bob 认为一个区间 $[l,r]$ 满足 $1\leq l\leq r\leq n$ 是正的，当且仅当其代表值 $b_l\times 2^{l-1}+b_{l+1}\times 2^l+\cdots+b_r\times 2^{r-1}> 0$，区间 $[l,r]$ 是负的则表示代表值 $<0$。

请问正区间个数和负区间个数相差多少？换言之，将正区间的个数记为 $A$，负区间的个数记为 $B$，求 $|A-B|$ 的值。

输入输出格式

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $b_{1\sim n}$。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例

4
4
1 -1 1 1
3
-1 -1 -1
2
1 -1
2
1 1

6
6
1
3

样例解释

样例 1 解释：

样例解释：对于第三组数据，区间 [1,1],[1,2],[2,2] 的代表值分别为 1,-1,-2，则A=1,B=2,|A-B|=1。

数据范围

对于 $30\%$ 的数据，$1\leq T\leq 10$，$1\leq n\leq 50$。

对于 $60\%$ 的数据，$1\leq T\leq 10$，$1\leq n\leq 1000$。

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$1\leq n\leq 10^5$，$\sum n\leq 3\times 10^5$，$b_i=1$ 或 $b_i=-1$。