题目内容

Tk 家的豪华大走廊按照从前到后的顺序总共有 $n$ 盏灯，编号为 $1 \sim n$，同时有 $n$ 个控制灯的开关编号为 $1 \sim n$，其中第 $i$ 个开关同时控制编号 $(i,i+1)$ 灯的状态，即按下第 $i$ 个开关时，编号 $(i,i+1)$ 的灯会变为另一种状态，特别地，第 $n$ 个开关只会控制第 $n$ 盏灯。给定一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$，其中 $a_i=1$ 时表示第 $i$ 盏灯处于发光状态，$a_i=0$ 表示第 $i$ 盏灯处于熄灭状态。

Tk 想知道最少需要操作几次开关才能使得所有灯都处于熄灭状态，请输出最小操作次数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ $(1 \le T \le 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$ $(1 \le n \le 2 \times 10^5)$ 表示灯的个数。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ $(0 \le a_i \le 1)$ 表示初始每盏灯的状态。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每一组测试数据，新起一行，输出一个整数表示最少操作开关次数。

样例1

输入

2
5
1 1 0 1 1
3
1 1 1

输出

2
2

说明

对于第二组测试数据需要按下编号 $(1,3)$ 的开关各一次。