#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
 
        // To store the minimum cost required to buy all figures
        long long min_cost = 0;
 
        // To accumulate costs in each possible visit
        long long visit_cost = 0;
 
        // Traverse the string and calculate costs
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                visit_cost += (i + 1);
                min_cost += (i + 1);
            }
        }
 
        // Deduct the cost of the highest-priced figure from each visit for discount
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] == '1' && s[i + 1] == '1') {
                min_cost -= max(i + 1, i + 2);
            }
        }
 
        cout << min_cost << endl;
    }
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbjsKICAgICAgICBzdHJpbmcgczsKICAgICAgICBjaW4gPj4gczsKCiAgICAgICAgLy8gVG8gc3RvcmUgdGhlIG1pbmltdW0gY29zdCByZXF1aXJlZCB0byBidXkgYWxsIGZpZ3VyZXMKICAgICAgICBsb25nIGxvbmcgbWluX2Nvc3QgPSAwOwogICAgICAgIAogICAgICAgIC8vIFRvIGFjY3VtdWxhdGUgY29zdHMgaW4gZWFjaCBwb3NzaWJsZSB2aXNpdAogICAgICAgIGxvbmcgbG9uZyB2aXNpdF9jb3N0ID0gMDsKICAgICAgICAKICAgICAgICAvLyBUcmF2ZXJzZSB0aGUgc3RyaW5nIGFuZCBjYWxjdWxhdGUgY29zdHMKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgICAgICBpZiAoc1tpXSA9PSAnMScpIHsKICAgICAgICAgICAgICAgIHZpc2l0X2Nvc3QgKz0gKGkgKyAxKTsKICAgICAgICAgICAgICAgIG1pbl9jb3N0ICs9IChpICsgMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIC8vIERlZHVjdCB0aGUgY29zdCBvZiB0aGUgaGlnaGVzdC1wcmljZWQgZmlndXJlIGZyb20gZWFjaCB2aXNpdCBmb3IgZGlzY291bnQKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG4gLSAxOyArK2kpIHsKICAgICAgICAgICAgaWYgKHNbaV0gPT0gJzEnICYmIHNbaSArIDFdID09ICcxJykgewogICAgICAgICAgICAgICAgbWluX2Nvc3QgLT0gbWF4KGkgKyAxLCBpICsgMik7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNvdXQgPDwgbWluX2Nvc3QgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==

NAoxCjEKNgoxMDExMDEKNwoxMTEwMDAxCjUKMTExMTEK

4
1
1
6
101101
7
1110001
5
11111