Задача . D. а-хорошая строка

Вам дана строка \(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'-хорошая строка.