定义：字符串```s``` 为一个```c-好串```（c 为一个字符）时，必须满足：

    1. 当|s| = 1 ，s = c

    2. 当|s| > 1, s 的左半部分为全为 c，右半部分为一个 ```(c+1)-好串``` 或者 s 的右半部分为全为 c，左半部分为一个 ```(c+1)-好串```

其中 |s| 代表 字符串 s 的长度。

举个例子：当 s=“cdbbaaaa"时，s 是一个 ```a-好串```

现在，给你一个字符串 s ( |s| = 2^k ),问最少替换多少个字符，使其为一个 ```a-好串```。

一个数字 t 表示给出多少个字符串 1 \le t \le 2 \cdot 10^4  

接下来 t 组数组，每行一个数字 n 表示字符串的长度， n = 2^k ， 1 \le n \le 131~072  接下来一个字符串S

 $t $行，每行一个数字，表示最少需要替换多少个字符，使其为一个 ```a-好串```。