F. Минимальное расстояние Хэмминга
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка$$$^\dagger$$$ $$$s$$$ длины $$$n$$$.

Бинарная строка $$$p$$$ той же длины $$$n$$$ называется хорошей, если для каждого $$$i$$$ ($$$1 \leq i \leq n$$$) существуют индексы $$$l$$$ и $$$r$$$ такие, что:

  • $$$1 \leq l \leq i \leq r \leq n$$$
  • $$$s_i$$$ является модой$$$^\ddagger$$$ строки $$$p_lp_{l+1}\ldots p_r$$$

Вам дана другая бинарная строка $$$t$$$ длины $$$n$$$. Найдите минимальное расстояние Хэмминга$$$^\S$$$ между $$$t$$$ и любой хорошей строкой $$$g$$$.

$$$^\dagger$$$ Бинарная строка — это строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Символ $$$c$$$ является модой строки $$$p$$$ длины $$$m$$$, если число вхождений $$$c$$$ в $$$p$$$ не меньше $$$\lceil \frac{m}{2} \rceil$$$. Например, $$$\mathtt{0}$$$ является модой $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ не является модой $$$\mathtt{010}$$$, и оба $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$ являются модами $$$\mathtt{011010}$$$.

$$$^\S$$$ Расстояние Хэмминга между строками $$$a$$$ и $$$b$$$ длины $$$m$$$ — это количество индексов $$$i$$$ таких, что $$$1 \leq i \leq m$$$ и $$$a_i \neq b_i$$$.

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

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

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) — длина бинарной строки $$$s$$$.

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

Третья строка каждого набора входных данных содержит бинарную строку $$$t$$$ длины $$$n$$$, состоящую из символов 0 и 1.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$, а также сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^8$$$.

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

Для каждого набора входных данных выведите минимальное расстояние Хэмминга между $$$t$$$ и любой хорошей строкой $$$g$$$.

Пример
Входные данные
3
3
000
000
4
0000
1111
6
111111
000100
Выходные данные
0
2
1
Примечание

В первом наборе входных данных $$$g=\mathtt{000}$$$ — это хорошая строка, которая имеет расстояние Хэмминга $$$0$$$ от $$$t$$$.

Во втором наборе входных данных $$$g=\mathtt{0011}$$$ — хорошая строка, имеющая расстояние Хэмминга $$$2$$$ от $$$t$$$. Можно доказать, что не существует хороших строк с расстоянием Хэмминга меньше $$$2$$$ от $$$t$$$.

В третьем наборе входных данных $$$g=\mathtt{001100}$$$ — хорошая строка, имеющая расстояние Хэмминга $$$1$$$ от $$$t$$$.