def check(half, string, n):
    a = ['a'] * half
    return string[0:half] == a or string[half:n] == a


for i in range(int(input())):
    n = int(input())
    string = list(input())
    if n == 1:
        if 'a' in string:
            print(0)
        else:
            print(1)
    elif n == 2:
        if string.count('a') == 2:
            print(0)
        else:
            print(1)
    else:
        half = n // 2
        if check(half, string, n):
            print(0)
        else:
            s1, s2 = string[0:half], string[half:n]
            count1, count2 = s1.count('a'), s2.count('a')
            if count1 == count2:
                print(count1 + count2)
            else:
                print(min([half - count1 + half - count2, n - string.count('a')]))
