a-Good String

Problem Source

CF 1385D

Problem Description

You are given a string $s$ of length $n$ consisting of lowercase letters, and $n = 2^k$ where $k$ is a non-negative integer.

A non-empty string $s$ is called $c$-$good$ ($c$ is some letter from $a$ to $z$) if it satisfies one of the following three conditions:

• $s$ has length $1$ and contains only the character $c$;
• $s$ has length greater than $1$, the first half of $s$ consists entirely of character $c$, and the second half is a $next(c)$-$good$ string, where $next(c)$ is the letter following $c$;
• $s$ has length greater than $1$, the first half is a $next(c)$-$good$ string, and the second half consists entirely of character $c$;

For example, aabc is a-$good$, and ffgheeee is e-$good$.

For the given string $s$, find the minimum number of characters you need to change in $s$ to make it an a-$good$ string.

Input Format

There are multiple test cases.

The first line contains an integer $T$, the number of test cases.

Each test case consists of two lines: the first line contains an integer $n$, and the second line contains a string $s$ of length $n$.

Output Format

For each test case, output one line containing an integer: the answer.

Sample Input

5
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z

Sample Output

0
7
4
5
1

Constraints

For $100\%$ of the data, $1 \leq T \leq 5, 1 \leq n \leq 131072$, and $n = 2^k$ where $k$ is a non-negative integer.