Вам дана строка $$$s[1 \dots n]$$$, состоящая из строчных латинских букв. Гарантируется, что $$$n = 2^k$$$ для некоторого целого числа $$$k \ge 0$$$.

Строка $$$s[1 \dots n]$$$ называется $$$c$$$-хорошей, если выполняется как минимум одно из следующих условий:

• Длина строки $$$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'-хорошей.

За один ход вы можете выбрать один индекс $$$i$$$ от $$$1$$$ до $$$n$$$ и заменить $$$s_i$$$ на любую строчную латинскую букву (любой символ от 'a' до 'z').

Ваша задача — найти минимальное количество ходов, необходимое, чтобы получить 'a'-хорошую строку из $$$s$$$ (т.е. $$$c$$$-хорошую строку для $$$c=$$$ 'a'). Гарантируется, что ответ всегда существует.

Вам нужно ответить на $$$t$$$ независимых наборов тестовых данных.

Еще один пример 'a'-хорошей строки является следующим. Например, рассмотрим строку $$$s = $$$«cdbbaaaa». Это 'a'-хорошая строка, потому что:

• вторая половина строки («aaaa») состоит только из символов 'a';
• первая половина строки («cdbb») — 'b'-хорошая строка, потому что:
  • вторая половина строки («bb») состоит только из символов 'b';
  • первая половина строки («cd») — 'c'-хорошая строка, потому что:
    • первая половина строки («c») состоит из единственного символа 'c';
    • вторая половина строки («d») — 'd'-хорошая строка.