A. Превратить в палиндром
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Али есть строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв. Также у него есть символ $$$c$$$, который является строчной латинской буквой. За одну монету он может выполнить следующую операцию над строкой $$$s$$$:

  • Для начала он выбирает индекс $$$1\le i\le n$$$.
  • После этого он заменяет $$$s_i$$$ на символ $$$c$$$.
Али хочет превратить строку $$$s$$$ в палиндром$$$^{\text{∗}}$$$, но не хочет тратить на это слишком много монет. Ваша задача — посчитать минимальное количество монет, которое он должен будет потратить, чтобы превратить строку $$$s$$$ в палиндром.

$$$^{\text{∗}}$$$Строка $$$t$$$ длины $$$m$$$ является палиндромом, если $$$t_i = t_{m-i+1}$$$ выполняется для каждого $$$1\le i\le m$$$

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ и строчную латинскую букву $$$c$$$ ($$$1\le n\le 100$$$) — длину строки $$$s$$$ и символ $$$c$$$.

Вторая строка каждого набора входных данных содержит строку $$$s$$$, состоящую из $$$n$$$ строчных латинских букв.

Выходные данные

Для каждого набора входных данных выведите одно число — минимальное количество монет, которое требуется потратить Али, чтобы строка стала палиндромом.

Пример
Входные данные
5
4 b
abca
3 p
xyx
5 e
abcbb
8 d
adbccbad
10 c
codeforces
Выходные данные
1
0
2
2
8
Примечание

В первом наборе входных данных за одну монету можно заменить $$$s_3$$$ на $$$\texttt{b}$$$. После замены строка равна $$$\texttt{abba}$$$, что уже является палиндромом. Можно доказать, что $$$1$$$ это минимальное количество монет, которое требуется потратить.

Во втором наборе входных данных строка $$$s$$$ уже является палиндромом.

В третьем наборе входных данных достаточно поменять $$$s_1$$$ и $$$s_5$$$ на $$$\texttt{e}$$$. После двух замен строка равна $$$\texttt{ebcbe}$$$, что уже является палиндромом.

В четвертом наборе входных данных за две монеты можно заменить $$$s_1$$$ и $$$s_7$$$.