题目描述

庞教授正在讲授关于 Fenwick 树（也称为二叉索引树）的课程。

在 Fenwick 树中，我们有一个长度为 $n$ 的数组 $c[1\ldots n]$，初始时全为零（对于任何 $1\le i\le n$，$c[i]=0$）。每次，庞教授可以对某个位置 $pos$（$1\leq pos \leq n$）和一个值 $val$ 调用以下过程：

def update(pos, val):
    while (pos <= n):
        c[pos] += val
        pos += pos & (-pos)

注意，对于任何正整数 pos，pos & (-pos) 等于 pos 的最大 2 的幂。

在这个过程中，$val$ 可以是任意实数。在调用了若干次（零次或多次）后，庞教授忘记了数组 $c$ 中的确切值。他只记得对于每个从 $1$ 到 $n$ 的 $i$，$c[i]$ 是否为零。庞教授想知道，在假设他的记忆是准确的情况下，他调用该过程的最小可能次数。

输入格式

第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n~(1 \le n \le 10 ^ 5)$。下一行包含一个长度为 $n$ 的字符串。如果 $c[i]$ 非零，则字符串的第 $i$ 个字符为 1，否则为 0。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出庞教授调用该过程的最小可能次数。可以证明答案总是存在的。

3
5
10110
5
00000
5
11111

3
0
3

提示

对于第一个例子，庞教授可以依次调用 update(1,1)，update(2,-1)，update(3,1)。

对于第三个例子，庞教授可以依次调用 update(1,1)，update(3,1)，update(5,1)。

题面翻译由 ChatGPT-4o 提供。