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

Дана строка $$$s$$$ состоящая только из $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

За одну операцию вы можете сделать следующее:

  • Выбрать подстроку$$$^{\text{∗}}$$$ $$$s$$$, которая является палиндромом$$$^{\text{†}}$$$ длины хотя бы $$$2$$$.
  • Удалить ровно один символ из выбранной подстроки.

Оставшиеся части строки конкатенируются в исходном порядке, образуя новое значение $$$s$$$.

Найдите минимальную возможную длину $$$s$$$, которой можно добиться применив операцию несколько (возможно ноль) раз.

$$$^{\text{∗}}$$$Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ можно получить из $$$b$$$ удалением нескольких (возможно нуля или всех) символов из начала и удалением нескольких (возможно нуля или всех) символов из конца.

$$$^{\text{†}}$$$Строка $$$a$$$ длины $$$m$$$ считается палиндромом, если $$$a_i = a_{m + 1 - i}$$$ для всех $$$1 \le i \le m$$$.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют описания наборов.

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

Вторая строка каждого набора содержит строку $$$s$$$ длины $$$n$$$. Гарантируется, что $$$s$$$ состоит только из $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

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

Для каждого набора входных данных выведите минимальную возможную длину строки $$$s$$$, которой можно добиться с помощью операций.

Пример
Входные данные
4
4
0000
3
110
6
110011
6
101100
Выходные данные
1
2
1
1
Примечание

В первом примере дана строка $$$\texttt{0000}$$$. Можно применить следующую последовательность операций:

  • Выбрать палиндромную подстроку $$$\texttt{0000}$$$. Удалить один $$$\texttt{0}$$$. Строка стала $$$\texttt{000}$$$.
  • Выбрать палиндромную подстроку $$$\texttt{000}$$$. Удалить один $$$\texttt{0}$$$. Строка стала $$$\texttt{00}$$$.
  • Выбрать палиндромную подстроку $$$\texttt{00}$$$. Удалить один $$$\texttt{0}$$$. Строка стала $$$\texttt{0}$$$.
В строке $$$\texttt{0}$$$ нет палиндромных подстрок длины хотя бы $$$2$$$, больше операций применить нельзя. Минимальная возможная длина равна $$$1$$$.

Во втором примере дана строка $$$\texttt{110}$$$.

  • Выбрать палиндромную подстроку $$$\texttt{11}$$$. Удалить одну $$$\texttt{1}$$$. Строка стала $$$\texttt{10}$$$.
В строке $$$\texttt{10}$$$ нет палиндромных подстрок длины хотя бы $$$2$$$, больше операций применить нельзя. Минимальная возможная длина равна $$$2$$$.