给定一个由小写拉丁字母组成的字符串 $$$s[1 \dots n]$$$。对于某个整数 $$$k \ge 0$$$,保证 $$$n = 2^k$$$。
如果至少满足以下三个条件之一,则字符串 $$$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)$$$ 好的字符串;
- $$$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)$$$ 好的字符串。
例如:“aabc”是“a”-好,“ffgheeee”是“e”-好。
在一步操作中,您可以从 $$$1$$$ 到 $$$n$$$ 中选择一个索引 $$$i$$$,并将 $$$s_i$$$ 替换为任何小写拉丁字母(从 'a' 到 'z' 的任何字符)。
你的任务是找到从 $$$s$$$ 获得 'a' 好的字符串(即 $$$c$$$-$$$c=$$$ 'a' 的好字符串)所需的最少移动次数。保证答案总是存在。
您必须回答 $$$t$$$ 独立测试用例。
'a'-good 字符串的另一个示例如下。考虑字符串 $$$s = $$$"cdbbaaaa"。这是一个“a”好的字符串,因为:
- 字符串的后半部分(“aaaa”)仅包含字符“a”;
- 字符串的前半部分(“cdbb”)是“b”-好的字符串,因为: 字符串的后半部分(“bb”)仅包含字符“b”; 字符串的前半部分(“cd”)是“c”良好的字符串,因为: 字符串的前半部分(“c”)仅包含字符“c”; 字符串的后半部分(“d”)是“d”-好字符串。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 131~072$$$) — $$$s$$$ 的长度。对于某个整数 $$$k \ge 0$$$,保证 $$$n = 2^k$$$。测试用例的第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。
保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。
输出
对于每个测试用例,打印答案 - 从 $$$s$$$ 获取“a”好字符串所需的最少移动次数(即 $$$c$$$-好字符串,其中 $$$c =$$$ 'a')。保证答案存在。
示例
输入 #1
6 8 bbdcaaaa 8 asdfghjk 8 ceaaaabb 8 bbaaddcc 1 z 2 ac
输出 #1
0 7 4 5 1 1