深境螺旋
题号：NC214199
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述



原神是最近非常火的一款游戏，jzk和火火也在玩。一天，jzk和火火正在组队挑战深境螺旋。深境螺旋中有个BOSS，编号从到。第个BOSS的类型为。如果第个BOSS很简单，则其类型为，否则，该BOSS很困难，其类型为。
在一个回合中，jzk和火火可以干掉1个或2个BOSS。（跳过回合是不被允许的，因此在一个回合中被干掉的BOSS至少为1个）jzk和火火轮流进行挑战，火火最先开始。
火火等级比较低，所以他无法干掉困难的BOSS（类型为），但他可以使用原石的力量，1个原石可以干掉1个困难的BOSS。
你的任务是求出按给定顺序干掉所有BOSS后，火火消耗的最少原石数量。

输入描述:

第一行一个整数，表示有组测试用例。
每个测试用例的第1行包含一个整数，第二行包含个整数，代表第个BOSS的类型。
数据保证的总和不超过

输出描述:

对于每个测试用例，输出火火消耗的最少原石数量。
示例1

输入

复制 
6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0

输出

复制 
2
2
2
2
1
0

说明

对于第一组样例，
第一轮，火火干掉了2个BOSS，并对第1个BOSS使用了一个原石；
第二轮，jzk干掉了第3个和第4个BOSS；
第三轮，火火干掉了第5个BOSS；
第四轮，jzk干掉了第6个和第7个BOSS；
第五轮，火火使用了一个原石干掉了最后一个BOSS。
因此干掉所有BOSS一共使用了2个原石。