D. Марк и лампочки
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Марк только что купил светильник из $$$n$$$ лампочек. Состояние лампочек можно описать бинарной строкой $$$s = s_1s_2\dots s_n$$$, где $$$s_i=\texttt{1}$$$ означает, что $$$i$$$-я лампочка включена, а $$$s_i=\texttt{0}$$$ означает, что $$$i$$$-я лампочка выключена.

К сожалению, лампочки сломаны, и Марк может выполнять единственную операцию, чтобы изменять состояние лампочек:

  • выбрать индекс $$$i$$$ из чисел $$$2,3,\dots,n-1$$$ такой, что $$$s_{i-1}\ne s_{i+1}$$$;
  • переключить $$$s_i$$$: если $$$s_i$$$ равно $$$\texttt{0}$$$, установить для $$$s_i$$$ значение $$$\texttt{1}$$$, и наоборот.

Марк хочет, чтобы состояние лампочек описывалось другой бинарной строкой $$$t$$$. Помогите Марку определить минимальное количество операций, чтобы достичь это состояние.

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3\leq n\leq 2\cdot 10^5$$$) — количество лампочек.

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

Третья строка каждого набора входных данных содержит бинарную строку $$$t$$$ длины $$$n$$$ — итоговое состояние лампочек.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных теста не превосходит $$$2\cdot 10^5$$$.

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

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

Пример
Входные данные
4
4
0100
0010
4
1010
0100
5
01001
00011
6
000101
010011
Выходные данные
2
-1
-1
5
Примечание

В первом наборе входных данных примера одна из последовательностей операций, обеспечивающая минимальное количество операций, следующая:

  • выбрать $$$i=3$$$, заменив $$$\texttt{01}\color{red}{\texttt{0}}\texttt{0}$$$ на $$$\texttt{01}\color{red}{\texttt{1}}\texttt{0}$$$;
  • выбрать $$$i=2$$$, заменив $$$\texttt{0}\color{red}{\texttt{1}}\texttt{10}$$$ на $$$\texttt{0}\color{red}{\texttt{0}}\texttt{10}$$$.

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

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

В четвертом наборе входных данных одна из последовательностей, обеспечивающая минимальное количество операций, выглядит следующим образом:

  • выбрать $$$i=3$$$, заменив $$$\texttt{00}\color{red}{\texttt{0}}\texttt{101}$$$ на $$$\texttt{00}\color{red}{\texttt{1}}\texttt{101}$$$;
  • выбрать $$$i=2$$$, заменив $$$\texttt{0}\color{red}{\texttt{0}}\texttt{1101}$$$ на $$$\texttt{0}\color{red}{\texttt{1}}\texttt{1101}$$$;
  • выбрать $$$i=4$$$, заменив $$$\texttt{011}\color{red}{\texttt{1}}\texttt{01}$$$ на $$$\texttt{011}\color{red}{\texttt{0}}\texttt{01}$$$;
  • выбрать $$$i=5$$$, заменив $$$\texttt{0110}\color{red}{\texttt{0}}\texttt{1}$$$ на $$$\texttt{0110}\color{red}{\texttt{1}}\texttt{1}$$$;
  • выбрать $$$i=3$$$, заменив $$$\texttt{01}\color{red}{\texttt{1}}\texttt{011}$$$ на $$$\texttt{01}\color{red}{\texttt{0}}\texttt{011}$$$.