Bot

题号：NC282700
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

有 $n$ 个房间，每个房间中有一个人类或一个 bot。

对于每个 $1\le i<n$ ，第 $i$ 个房间中的人类或 bot 会对第 $i+1$ 个房间进行观察，并告诉你第 $i+1$ 个房间中是人类还是 bot。

具体地，给定一个长度为 $n-1$ 的 $01$ 串 $a$ 。 $a_i=1$ 当且仅当第 $i$ 个房间中的人类或 bot 认为第 $i+1$ 个房间中是 bot。

人类总是能做出正确的判断，而 bot 不一定能。利用以上信息求出至少有多少个 bot。

测试点中有多组数据。

$1\le T\le 10^5,n\ge 2,\sum n\le 10^6$ 。

输入描述:

第一行，一个整数，表示数据组数 。

对于每组数据：

第一行，一个整数，表示 。

第二行，一个长度为  的  串，表示 。

输出描述:

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

示例1

输入

复制

输出

复制

1
2
3