Prof. Pang 正在讲授关于树状数组（Fenwick tree，也称为二叉索引树）的课程。

在树状数组中，我们有一个长度为 $n$ 的数组 $c[1 \dots n]$，初始时全为零（对于任意 $1 \le i \le n$，都有 $c[i] = 0$）。每次，Prof. Pang 可以针对某个位置 $pos$ ($1 \le pos \le n$) 和数值 $val$ 调用以下过程：

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

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

在该过程中，$val$ 可以是任何实数。在调用该过程若干次（零次或多次）后，Prof. Pang 忘记了数组 $c$ 中的确切数值。他只记得对于每个 $i$ ($1 \le i \le n$)，$c[i]$ 是否为零。假设他的记忆是准确的，Prof. Pang 想知道他调用该过程的最少次数是多少。

输入格式

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

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

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

输出格式

对于每个测试用例，输出 Prof. Pang 调用该过程的最少次数。可以证明答案总是存在的。

样例

输入 1

3
5
10110
5
00000
5
11111

输出 1

3
0
3

说明

对于第一个样例，Prof. Pang 可以依次调用 update(1,1)，update(2,-1)，update(3,1)。

对于第三个样例，Prof. Pang 可以依次调用 update(1,1)，update(3,1)，update(5,1)。