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}。

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

对于 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。