题目内容

停车场沿一条直线依次布置了 n 个车位指示牌。第 $i$ 个指示牌的状态为整数 $a_i$：0 表示空闲，1 表示占用。同时有 n 个控制器，编号为 $1 \sim n$。按下第 $i$ 个控制器时，第 $i$ 个和第 $i+1$ 个指示牌会同时翻转状态（0 变为 1，1 变为 0）；特别地，第 n 个控制器只会翻转第 n 个指示牌。每个控制器可以按下任意次，目标是使所有指示牌都变为 0。求最少需要按下控制器的总次数。数据范围：测试组数 $T$ 满足 $1 \le T \le 10^4$；每组中 $1 \le n \le 2 \times 10^5$，$a_i$ 只能为 0 或 1；单个测试文件中所有 n 之和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 T，表示测试数据组数，满足 $1 \le T \le 10^4$。每组测试数据格式如下：第一行包含一个整数 n，表示指示牌数量，满足 $1 \le n \le 2 \times 10^5$；第二行包含 n 个整数 $a_1, a_2, \dots, a_n$，每个 $a_i$ 只能为 0 或 1。单个测试文件中所有 n 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示使所有指示牌变为 0 所需的最少按压次数。

样例1

输入

3
1
0
4
1 0 1 0
6
1 1 1 0 0 1

输出

0
2
4

说明

从左到右确定每个控制器是否按下：第 1 个指示牌只受第 1 个控制器影响，因此必须按下当且仅当 $a_1=1$；之后第 $i$ 个控制器由 $x_i=a_i \oplus x_{i-1}$ 唯一确定。

第一组：只有一个空闲指示牌 $a=[0]$，无需按压，答案为 0。

第二组：$a=[1,0,1,0]$，依次得到 $x=[1,1,0,0]$，按下前两个控制器即可全部变为 0，答案为 2。

第三组：$a=[1,1,1,0,0,1]$，依次得到 $x=[1,0,1,1,1,0]$，共按下 4 次。

样例2

输入

2
1
1
3
0 0 0

输出

1
0

说明

第一组：单个占用指示牌必须按一次第 1 个控制器，答案为 1。

第二组：三个指示牌已经全是 0，所有 $x_i=0$，答案为 0。

样例3

输入

2
5
1 0 0 1 1
6
0 1 0 1 0 1

输出

4
3

说明

第一组：$a=[1,0,0,1,1]$。前缀异或依次为 $1,1,1,0,1$，其中值为 1 的位置有 4 个，答案为 4。

第二组：$a=[0,1,0,1,0,1]$。前缀异或依次为 $0,1,1,0,0,1$，其中值为 1 的位置有 3 个，答案为 3。