# Coding is about expressing your feeling and there is always a better way to express your feeling _feelme
import sys,math
# sys.stdin,sys.stdout=open('input.txt','r'),open('output.txt','w')
from sys import stdin,stdout;mod=int(1e9 + 7)
from collections import deque,defaultdict;from copy import deepcopy;from math import ceil,floor,inf,sqrt,factorial,gcd,log2
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# np.set_printoptions(sign=' ',legacy='1.13') # legacy add space at sign positoin


def good(a,nn):
    if nn==0:
        return 0
    if nn==1:
        if a[0]=='a':
            return 0
        else:
            return 1
    if nn==2:
        if a[0]=='a' and a[1]=='a':
            return 0
        elif a[0]=='a' or a[1]=='a':
            return  1
        else:
            return 2
    return good(a[0:nn//2],nn//2)+good(a[nn//2::],nn//2)
if __name__=='__main__':
    for _ in range(ii1()):
        n = ii1()
        s = is1()
        if n==1:
            if s[0]=='a':
                print(0)
            else:
                print(1)
        elif n==2:
            if s[0]=='a' and s[1]=='a':
                print(0)
            elif s[0]=='a' or s[1]=='a':
                print(1)
            else:
                print(1)
        elif s[0:n//2]=='a'*(n//2) or s[n//2::]=='a'*(n//2):
            print(0)
        else:
            a=good(s[0:n//2],n//2)+good(s[n//2::],n//2)
            print(a)


