题目描述

给定一个由小写拉丁字母组成的字符串 $s[1 \dots n]$。保证 $n = 2^k$，其中 $k \ge 0$。

如果字符串 $s[1 \dots n]$ 满足以下三个条件之一，则称其为 $c$-good 字符串：

• $s$ 的长度为 $1$，且唯一的字符为 $c$（即 $s_1 = c$）；
• $s$ 的长度大于 $1$，且前一半全为字符 $c$（即 $s_1 = s_2 = \dots = s_{\frac{n}{2}} = c$），并且后一半（即 $s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n$）是 $(c+1)$-good 字符串；
• $s$ 的长度大于 $1$，且后一半全为字符 $c$（即 $s_{\frac{n}{2} + 1} = s_{\frac{n}{2} + 2} = \dots = s_n = c$），并且前一半（即 $s_1s_2 \dots s_{\frac{n}{2}}$）是 $(c+1)$-good 字符串。

例如："aabc" 是 'a'-good 字符串，"ffgheeee" 是 'e'-good 字符串。

每次操作，你可以选择一个下标 $i$（$1 \le i \le n$），将 $s_i$ 替换为任意一个小写拉丁字母（'a' 到 'z' 之间的任意字符）。

你的任务是，求将 $s$ 变为 'a'-good 字符串（即 $c$-good 字符串，$c =$ 'a'）所需的最少操作次数。保证一定存在解。

你需要回答 $t$ 组独立的测试用例。

另一个 'a'-good 字符串的例子如下。考虑字符串 $s =$ "cdbbaaaa"。它是一个 'a'-good 字符串，因为：

• 字符串的后一半 "aaaa" 全为字符 'a'；
• 前一半 "cdbb" 是 'b'-good 字符串，因为：
  • 后一半 "bb" 全为字符 'b'；
  • 前一半 "cd" 是 'c'-good 字符串，因为：
    • 前一半 "c" 全为字符 'c'；
    • 后一半 "d" 是 'd'-good 字符串。

输入格式

输入的第一行为一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来有 $t$ 组测试用例。

每组测试用例的第一行为一个整数 $n$（$1 \le n \le 131072$），表示字符串 $s$ 的长度。保证 $n = 2^k$，其中 $k \ge 0$。第二行为一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

输出格式

对于每组测试用例，输出一个整数，表示将 $s$ 变为 'a'-good 字符串所需的最少操作次数。保证一定存在解。

输入输出样例 #1

6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac

0
7
4
5
1
1