2021 ICPC Asia East Continent Final L. 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…n]of length nn which is initially all-zero (c[i]=0 for any 1≤i≤n). Each time, Prof. Pang can call the following procedure for some position pospos (1≤pos≤n) and value valval:

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

Note that pos & (-pos) equals to the maximum power of 2that divides pos for any positive integer pos.

In the procedure, valval can be any real number. After calling it some (zero or more) times, Prof. Pang forgets the exact values in the array c. He only remembers whether c[i]is zero or not for each i from 1 to n. Prof. Pang wants to know what is the minimum possible number of times he called the procedure assuming his memory is accurate.

Input

The first line contains a single integer T (1≤T≤105)denoting the number of test cases.

For each test case, the first line contains an integer n (1≤n≤105). The next line contains a string of length n. The ii-th character of the string is 1 if c[i] is nonzero and 0 otherwise.

It is guaranteed that the sum of nn over all test cases is no more than 106106.

Output

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.

Example

input

Copy

3
5
10110
5
00000
5
11111

output

Copy

3
0
3

Note

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.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int lowbit(int x)
{
    return x&(-x);
}
void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int>cnt(n+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i-1]=='1')
        {
            if(i+lowbit(i)<=n)
            {
                cnt[i+lowbit(i)]++;
            }
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i-1]=='0'&&cnt[i]==1)
        {
            sum++;
        }
        else if(s[i-1]=='1'&&cnt[i]==0)
        {
            sum++;
        }
    }
    cout<<sum<<"\n";
}
signed main()
{
    /*ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);*/
     int _;
     cin>>_;
     while(_--)
     {
         solve();
     }
 
    return 0;
}