新二进制

题目描述

Bob 研究出一种新二进制：每一位只能是 $-1$ 或 $1$。一个 $n$ 位新二进制数为 $b_1 \times 2^0 + b_2 \times 2^1 + \cdots + b_n \times 2^{n-1}$。

一个区间 $[l,r]$ 的值为其对应位加权和。请问正区间个数 $A$ 和负区间个数 $B$ 之差 $|A - B|$。

输入格式

第一行 $T$ 表示数据组数。每组：第一行 $n$，第二行 $n$ 个整数 $b_{1\sim n} \in \{-1, 1\}$。

输出格式

每组输出一行 $|A - B|$。

数据范围

$1 \leq T \leq 10^5$，$1 \leq n \leq 10^5$，$\sum n \leq 3 \times 10^5$

样例

样例输入

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

样例输出

6
6
1
3