You are given a string $s[1 \dots n]$ consisting of lowercase Latin letters. It is guaranteed that $n = 2^k$ for some integer $k \ge 0$.

The string $s[1 \dots n]$ is called $c$-good if at least one of the following three conditions is satisfied:  The length of $s$ is $1$, and it consists of the character $c$ (i.e. $s_1=c$); The length of $s$ is greater than $1$, the first half of the string consists of only the character $c$ (i.e. $s_1=s_2=\dots=s_{\frac{n}{2}}=c$) and the second half of the string (i.e. the string $s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n$) is a $(c+1)$-good string;  The length of $s$ is greater than $1$, the second half of the string consists of only the character $c$ (i.e. $s_{\frac{n}{2} + 1}=s_{\frac{n}{2} + 2}=\dots=s_n=c$) and the first half of the string (i.e. the string $s_1s_2 \dots s_{\frac{n}{2}}$) is a $(c+1)$-good string. 

For example: "aabc" is 'a'-good, "ffgheeee" is 'e'-good.

In one move, you can choose one index $i$ from $1$ to $n$ and replace $s_i$ with any lowercase Latin letter (any character from 'a' to 'z').

Your task is to find the minimum number of moves required to obtain an 'a'-good string from $s$ (i.e. $c$-good string for $c=$ 'a'). It is guaranteed that the answer always exists.

You have to answer $t$ independent test cases.

Another example of an 'a'-good string is as follows. Consider the string $s = $"cdbbaaaa". It is an 'a'-good string, because:  the second half of the string ("aaaa") consists of only the character 'a';  the first half of the string ("cdbb") is 'b'-good string, because:   the second half of the string ("bb") consists of only the character 'b';  the first half of the string ("cd") is 'c'-good string, because:   the first half of the string ("c") consists of only the character 'c';  the second half of the string ("d") is 'd'-good string.   


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 131~072$) — the length of $s$. It is guaranteed that $n = 2^k$ for some integer $k \ge 0$. The second line of the test case contains the string $s$ consisting of $n$ lowercase Latin letters.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the minimum number of moves required to obtain an 'a'-good string from $s$ (i.e. $c$-good string with $c =$ 'a'). It is guaranteed that the answer exists.


-----Example-----
Input
6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac

Output
0
7
4
5
1
1

Difficulty: introductory

Starter code:

Solutions:
# coding: utf-8
# Your code here!

def solve(s, c):
    if(len(s)==1):
        if s[0]==c:
            return 0
        else:
            return 1
    ans1 = sum([i!=c for i in s[:len(s)//2]]) + solve(s[len(s)//2:],chr(ord(c)+1))
    ans2 = sum([i!=c for i in s[len(s)//2:]]) + solve(s[:len(s)//2],chr(ord(c)+1))
    return min(ans1, ans2)
    
    
for _ in range(int(input())):
    input()
    print(solve(input(),'a'))

a = None

def subsolve(l, r, c):
    nonlocal a
    if r - l <= 1:
        return 0 if a[l] == c else 1
    mid = (l + r) // 2
    u = subsolve(mid, r, c + 1)
    for i in range(l, mid):
        if a[i] != c:
            u += 1
    v = subsolve(l, mid, c + 1)
    for i in range(mid, r):
        if a[i] != c:
            v += 1
    return min(u, v)

def solve():
    nonlocal a
    n = int(input())
    a = list(map(ord, input()))
    print(subsolve(0, n, ord('a')))

t = int(input())
for _ in range(t):
    solve()

def make_good(s, c):
    if len(s) == 1:
        return int(s[0] != c)
    
    mid = len(s) // 2
    
    ans = len(s)
    for x, y, z, t in [(0, mid, mid, len(s)), (mid, len(s), 0, mid)]:
        cur_ans = 0
        for i in s[x:y]:
            cur_ans += int(i != c)
        cur_ans += make_good(s[z:t], chr(ord(c) + 1))
        ans = min(ans, cur_ans)
    return ans
    
for testcase in range(int(input())):
    n = int(input())
    s = input().strip()
    print(make_good(s, 'a'))
    


def find(st,count,ans,low,high,char):
	#print(st,low,high,"ss")
	if high-low==0:
		if chr(char)==st[high]:
			ans.append(count)
		else:
			ans.append(count+1)
	else:
		check=0
		mid=(high+low)//2
		for k in st[low:mid+1]:
			if k!=chr(char):
				check+=1
		find(st,count+check,ans,mid+1,high,char+1)
		check=0
		for k in st[mid+1:high+1]:
			if k!=chr(char):
				check+=1
		find(st,count+check,ans,low,mid,char+1)

for i in range(int(input())):
	n=int(input())
	st=input()
	ans=[]
	find(st,0,ans,0,n-1,97)
	print(min(ans))

def getAns(c, lo, hi, prefixCnt):
    if lo+1 == hi:
        return 1 - (prefixCnt[c][hi] - prefixCnt[c][lo])
    mid = (lo + hi) // 2
    ans = 1<<30
    ans = min(ans, (hi - lo) // 2 - (prefixCnt[c][mid] - prefixCnt[c][lo]) + getAns(c+1, mid, hi, prefixCnt))
    ans = min(ans, (hi - lo) // 2 - (prefixCnt[c][hi] - prefixCnt[c][mid]) + getAns(c+1, lo, mid, prefixCnt))
    return ans
    
for _ in range(int(input())):
    n = int(input())
    s = input()
    prefixCnt = [[0 for _ in range(n+1)] for _ in range(26)]
    for i in range(n):
        for j in range(26):
            prefixCnt[j][i+1] = prefixCnt[j][i]
        index = ord(s[i]) - ord('a')
        prefixCnt[index][i+1] += 1
    print(getAns(0, 0, n, prefixCnt))


alphabet = 'abcdefghijklmnopqrstuvwxyz'


def recursion(s, start, end, height):
    if end - start == 1:
        if s[start] == alphabet[height]:
            return 0
        else:
            return 1
    else:
        middle = (start + end) // 2
        return min(
            recursion(s, middle, end, height + 1) + (end - start) // 2 - s[start:middle].count(alphabet[height]),
            recursion(s, start, middle, height + 1) + (end - start) // 2 - s[middle:end].count(alphabet[height]),
        )


def solve():
    n = int(input())
    s = input()
    print(recursion(s, 0, n, 0))


for _ in range(int(input())):
    solve()


def want(l,r,depth):

    ret = [0] * 26
    if l + 1 == r:
        ret[ad[s[l]]] += 1

        if alp[depth] == s[l]:
            return 0,ret
        else:
            return 1,ret
    else:

        Lmini , Llis = want(l,(l+r)//2,depth+1)
        Rmini , Rlis = want((l+r)//2 , r , depth+1)

        LL = ((l+r)//2-l) - Llis[depth]
        RR = ((l+r)//2-l) - Rlis[depth]

        for i in range(26):
            Llis[i] += Rlis[i]
        return min(Lmini+RR , Rmini+LL) , Llis

from sys import stdin

alp = "abcdefghijklmnopqrstuvwxyz"
ad = {}
for i in range(26):
    ad[alp[i]] = i

tt = int(stdin.readline())

for loop in range(tt):

    n = int(stdin.readline())
    s = stdin.readline()

    ans,tmp = want(0,n,0)
    print (ans)


import math
from collections import deque
from sys import stdin, stdout
from string import ascii_letters
input = stdin.readline
#print = stdout.write
letters = ascii_letters[:26]

for _ in range(int(input())):
    n = int(input())
    nx = input().strip()
    buff = deque()
    res = 9999999
    buff.append((nx, 0, 0))
    while len(buff):
        x = buff.popleft()
        if len(x[0]) == 1:
            if x[0][0] != letters[x[1]]:
                res = min(res, x[2] + 1)
            else:
                res = min(res, x[2])
            continue
        left = x[0][:len(x[0]) // 2]
        right = x[0][len(x[0]) // 2:]
        buff.append((left, x[1] + 1, x[2] + (len(right) - right.count(letters[x[1]]))))
        buff.append((right, x[1] + 1, x[2] + (len(left) - left.count(letters[x[1]]))))
    print(res)


import sys
# sys.stdin = open("in", "r")
# sys.stdout = open("out", "w")

inp = sys.stdin.read().split(); ii = 0
t = int(inp[0]); ii += 1
for _ in range(t):
	n = int(inp[ii]); ii += 1
	s = inp[ii]; ii += 1
	if n == 1:
		if 'a' in s:
			print(0)
		else:
			print(1)
		continue
	stack = [[0, n, ord('a'), 0]]
	ans = n
	while stack:
		l, r, c, cost = stack[-1]
		stack.pop()
		if r-l == 1:
			if chr(c) in s[l:r]:
				ans = min(ans, cost)
			else:
				ans = min(ans, cost+1)
			continue
		
		mid = (l+r)//2
		stack.append([l, mid, c+1, r-mid+cost-s[mid:r].count(chr(c))])
		stack.append([mid, r, c+1, mid-l+cost-s[l:mid].count(chr(c))])
	print(ans)


def solve(n, s):
    def _doit(l, r, c):
        ch = chr(ord('a') + c)
        if l+1 == r:
            return int(s[l] != ch)
        mid = l + (r-l)//2
        non1 = sum(int(s[i] != ch) for i in range(l, mid))
        non2 = sum(int(s[i] != ch) for i in range(mid, r))
        return min(non1 + _doit(mid, r, c+1), non2 + _doit(l, mid, c+1))
    return _doit(0, n, 0)

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    # a = list(map(int, input().split()))
    # x, y, z = map(int, input().split())
    print(solve(n, s))

def f(s,symb):
    if len(s)==1:return int(s[0]!=symb)
    f1=f2=0
    c1=''
    c2=''
    for i in range(len(s)//2):f1+=int(s[i]!=symb);c1+=s[i]
    for i in range(len(s)//2,len(s)):f2+=int(s[i]!=symb);c2+=s[i]
    ns=chr(ord(symb)+1)
    return min(f1+f(c2,ns),f2+f(c1,ns))
for _ in range(int(input())):
    n=int(input())
    s=input()
    print(f(s,'a'))

alph="abcdefghijklmnopqrstuvwqyz"
def solve(s,i,n):
    if n==1:
        if s[0]==alph[i]:
            return 0
        else:
            return 1
    else:
        c1=0
        c2=0
        s1=s[0:n//2]
        s2=s[n//2:n]
        for x in s1:
            if x!=alph[i]:
                c1+=1
        for x in s2:
            if x!=alph[i]:
                c2+=1
        return min(c1+solve(s2,i+1,n//2),c2+solve(s1,i+1,n//2))
import sys
input = sys.stdin.readline
for f in range(int(input())):
    n=int(input())
    s=input()
    s=s[0:n]
    print(solve(s,0,n))

import math
#r,g,b=map(int,input().split())
#list1 = input().split()
#for i in range(len(list1)):
#    list1[i] = int(list1[i])
#print(list1)
#print(r, g, b)
# arr = [[0 for x in range(columns)] for y in range(rows)]

lookup = "abcdefghijklmnopqrstuvwxyz"
t=int(input())

def helper(string, k):
    n = len(string)
    m = n//2
    if(n == 1 and string  == lookup[k]):
        return 0
    elif(n == 1):
        return 1
    else:
        front1 = helper(string[0:m], k+1)
        back1 = helper(string[m:n], k+1)
        for i in range(m):
            if(string[i] != lookup[k]):
                back1 += 1
        for i in range(m):
            if(string[m + i] != lookup[k]):
                front1 += 1
        return min(front1, back1)

for i in range(t):
    n = int(input())
    string = input()
    print(helper(string, 0))