描述

给你一个长度为 $n (n=2^k，k≥0)$的小写字母字符串 $s[1 \dots n]$。
定义：字符串$s$为一个 c-好串（$c$为一个字符）时，必须满足下面三个条件中一个：
$1.$ 当 $|s|=1$时，字符串$s$包含字符$c$，即$s[1] = c$；
$2.$ 当 $|s|>1$时，$s$的左半部分为全为字符$c$，右半部分为一个 (c+1)-好串 ,$c+1$表示字符$c$的下一个字符。
$3.$ 当 $|s|>1$时，$s$的右半部分为全为字符$c$，左半部分为一个 (c+1)-好串 ,$c+1$表示字符$c$的下一个字符。
其中 $|s|$代表字符串$s$的长度。
例如： $"aabc"$ $is$ 'a'-好串， $"ffgheeee"$ $is$ 'e'-好串。
现在，给你一个字符串 $s(|s|=2^k)$，问最少替换多少个字符，使其为一个 'a'-好串。

格式

输入格式

第一行一个整数$t$，表示测试数据组数。每组测试数据：
第一行一个整数$n$，表示字符串$s$的长度，保证 $n=2^k$ 。
第二行一个长度为$n$的全为小写字母字符串$s$。

输出格式

输出$t$行，每行对应一组测试数据包含一个整数，表示最少需要替换的字符个数。

样例1

输入样例1

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

输出样例1

0
7
4
5
1

限制

$100\%$ 的数据：$1≤t≤2×10^4, 1≤n≤131072，$$\sum$$n≤2×10^5。$