import sys
range = xrange
input = raw_input

def mapper(A):
    return [ord(c) - ord('a') for c in A]
def remapper(A):
    return ''.join(chr(c + ord('a')) for c in A)

t = int(input())
for _ in range(t):
    n = int(input())
    A = mapper(input())

    DP = [0] * (2 * n)
    L = [0] * (2 * n)
    R = [0] * (2 * n)
    for i in reversed(range(1, 2 * n)):
        c = i.bit_length() - 1
        l = L[i] = i - n if i >= n else L[2 * i]
        r = R[i] = i - n if i >= n else R[2 * i + 1]
        r += 1
        mid = l + r >> 1

        if i >= n:
            DP[i] += A[i - n] != c
        else:
            alt1 = DP[2 * i + 1] + sum(A[j] != c for j in range(l,mid))
            alt2 = DP[2 * i    ] + sum(A[j] != c for j in range(mid,r))
            DP[i] = min(alt1,alt2)
    print DP[i]
