P9883 [EC Final 2021] Fenwick Tree

Prof. Pang is giving a lecture on the Fenwick tree (also called binary indexed tree). In a Fenwick tree, we have an array $c[1\ldots n]$ of length $n$ which is initially all-zero ($c[i]=0$ for any $1\le i\le n$). Each time, Prof. Pang can call the following procedure for some position $pos$ ($1\leq pos \leq n$) and value $val$: ```cpp def update(pos, val): while (pos

The first line contains a single integer $T~(1 \le T \le 10^5)$ denoting the number of test cases. For each test case, the first line contains an integer $n~(1 \le n \le 10 ^ 5)$. The next line contains a string of length $n$. The $i$-th character of the string is `1` if $c[i]$ is nonzero and `0` otherwise. It is guaranteed that the sum of $n$ over all test cases is no more than $10^6$.

For each test case, output the minimum possible number of times Prof. Pang called the procedure. It can be proven that the answer always exists.

For the first example, Prof. Pang can call `update(1,1)`, `update(2,-1)`, `update(3,1)` in order. For the third example, Prof. Pang can call `update(1,1)`, `update(3,1)`, `update(5,1)` in order.