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

Изначально у Тимура есть бинарная строка $$$^{\dagger}$$$ $$$s$$$ (возможно длины $$$0$$$). Он применил следующую операцию несколько раз (возможно ноль):

  • Приписать $$$\texttt{0}$$$ к одному из концов строки и $$$\texttt{1}$$$ к другому концу строки. Например, из строки $$$\texttt{1011}$$$, мы можем получить или $$$\color{red}{\texttt{0}}\texttt{1011}\color{red}{\texttt{1}}$$$, или $$$\color{red}{\texttt{1}}\texttt{1011}\color{red}{\texttt{0}}$$$.

Вам дана строка, которая получилась у Тимура. Какая наименьшая возможная длина строки могла быть вначале (до выполнения всех операций)?

$$$^{\dagger}$$$ Бинарная строка это строка (возможно пустая), содержащая только символы $$$\texttt{0}$$$ или $$$\texttt{1}$$$.

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

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

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — длину строки Тимура после выполнения всех операций.

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

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

Для каждого набора входных данных выведите единственное неотрицательное целое число — наименьшую возможную длину изначальной строки Тимура. Обратите внимание, что изначальная строка Тимура может быть пустой, в этом случае выведите $$$0$$$.

Пример
Входные данные
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
Выходные данные
1
2
5
0
3
1
0
2
4
Примечание

В первом наборе входных данных, кратчайшая изначальная строка Тимура это $$$\texttt{0}$$$. К ней он применил следующую операцию: $$$\texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}}$$$.

Во втором наборе, кратчайшая изначальная строка Тимура это $$$\texttt{11}$$$. К ней он применил следующую операцию: $$$\texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}}$$$.

В третьем наборе, кратчайшая изначальная строка Тимура это $$$\texttt{10101}$$$ и он не применял к ней никаких операций.

В четвертом наборе, кратчайшая изначальная строка Тимура это пустая строка (обозначим её как $$$\varepsilon$$$). К ней он применил следующие операции: $$$\varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}}$$$.

В пятом наборе, кратчайшая изначальная строка Тимура это $$$\texttt{101}$$$. К ней он применил следующие операции: $$$\texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}}$$$.