描述

给你一个长度为 \(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。\)