def getSwaps(c, s):
    positions = [i for i, char in enumerate(s) if char == c]
 
    if len(positions) <= 1:
        return 0
 
    offsets = [pos - i for i, pos in enumerate(positions)]
    offsets.sort()
    median = offsets[len(offsets) // 2]
    swaps = sum(abs(offset - median) for offset in offsets)
 
    return swaps
 
 
def solve():
    n = int(input())
    s = input()
 
    swapsA = getSwaps('a', s)
    swapsB = getSwaps('b', s)
 
    print(min(swapsA, swapsB))
 
 
def main():
    num_test_cases_str = input()
    if not num_test_cases_str: return
    num_test_cases = int(num_test_cases_str)
    for _ in range(num_test_cases):
        solve()
 
main()

ZGVmIGdldFN3YXBzKGMsIHMpOgogICAgcG9zaXRpb25zID0gW2kgZm9yIGksIGNoYXIgaW4gZW51bWVyYXRlKHMpIGlmIGNoYXIgPT0gY10KICAgIAogICAgaWYgbGVuKHBvc2l0aW9ucykgPD0gMToKICAgICAgICByZXR1cm4gMAogICAgCiAgICBvZmZzZXRzID0gW3BvcyAtIGkgZm9yIGksIHBvcyBpbiBlbnVtZXJhdGUocG9zaXRpb25zKV0KICAgIG9mZnNldHMuc29ydCgpCiAgICBtZWRpYW4gPSBvZmZzZXRzW2xlbihvZmZzZXRzKSAvLyAyXQogICAgc3dhcHMgPSBzdW0oYWJzKG9mZnNldCAtIG1lZGlhbikgZm9yIG9mZnNldCBpbiBvZmZzZXRzKQogICAgCiAgICByZXR1cm4gc3dhcHMKCgpkZWYgc29sdmUoKToKICAgIG4gPSBpbnQoaW5wdXQoKSkKICAgIHMgPSBpbnB1dCgpCgogICAgc3dhcHNBID0gZ2V0U3dhcHMoJ2EnLCBzKQogICAgc3dhcHNCID0gZ2V0U3dhcHMoJ2InLCBzKQogICAgCiAgICBwcmludChtaW4oc3dhcHNBLCBzd2Fwc0IpKQoKCmRlZiBtYWluKCk6CiAgICBudW1fdGVzdF9jYXNlc19zdHIgPSBpbnB1dCgpCiAgICBpZiBub3QgbnVtX3Rlc3RfY2FzZXNfc3RyOiByZXR1cm4KICAgIG51bV90ZXN0X2Nhc2VzID0gaW50KG51bV90ZXN0X2Nhc2VzX3N0cikKICAgIGZvciBfIGluIHJhbmdlKG51bV90ZXN0X2Nhc2VzKToKICAgICAgICBzb2x2ZSgpCgptYWluKCk=

NQo0CmFiYWIKNgpiYWJhYmEKNwphYmFiYWJhCjIKYWIKMQpiCg==

5
4
abab
6
bababa
7
abababa
2
ab
1
b