a-Good String

题目来源

CF 1385D

题目描述

给你一个长度为 $n$ 的由小写字母组成的字符串 $s$，保证 $n=2^k$，其中 $k$ 为大于等于零的整数。

一个非空字符串 $s$ 被称为 $c$-$good$（$c$ 为 $a...z$ 中的某个字母）的，需要满足下列三个条件之一：

• $s$ 长度为 $1$，且只含有 $c$ 字符；
• $s$ 长度大于 $1$，且 $s$ 的前一半全为字符 $c$，后一半为 $next(c)$-$good$ 的字符串，其中 $next(c)$ 表示 $c$ 后面的那一个字母；
• $s$ 长度大于 $1$，且 $s$ 的前一半为 $next(c)$-$good$ 的字符串，后一半全为字符 $c$；

例如 aabc 是 a-$good$ 的，ffgheeee 是 e-$good$ 的。

对于给定的字符串 $s$，请求出最少改变 $s$ 中几个字符可以把它变成 a-$good$ 的字符串。

输入格式

输入有多组询问。

第一行一个整数 $T$ 表示数据组数。

对于每组数据包含两行，第一行一个整数 $n$，第二行一个长度为 $n$ 的字符串 $s$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例输入

5
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z

样例输出

0
7
4
5
1

数据范围

对于 $100\%$ 的数据，保证 $1\leq T\leq 5, 1\leq n\leq 131072$，保证 $n=2^k$，其中 $k$ 为大于等于零的整数。