C2. Marenol (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии требуется определить минимальное количество операций, чтобы преобразовать $$$a$$$ в $$$b$$$.

Юсеф дал вам две двоичные строки, $$$a$$$ и $$$b$$$, одинаковой длины $$$n$$$.

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

  • Выбрать подстроку$$$^{\text{∗}}$$$ в $$$a$$$, равную $$$\texttt{001}$$$, и заменить её на $$$\texttt{100}$$$, или наоборот (то есть $$$\texttt{001} \rightarrow \texttt{100}$$$ или $$$\texttt{100} \rightarrow \texttt {001}$$$).
  • Выбрать подстроку в $$$a$$$, равную $$$\texttt{110}$$$, и заменить её на $$$\texttt{011}$$$, или наоборот (то есть $$$\texttt{011} \rightarrow \texttt{110}$$$ или $$$\texttt{110} \rightarrow \texttt {011}$$$).

Ваша задача — определить минимальное количество операций, необходимое для преобразования строки $$$a$$$ в строку $$$b$$$. Если преобразовать $$$a$$$ в $$$b$$$ с помощью данных операций невозможно, вместо этого выведите $$$-1$$$.

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину каждой строки.

Вторая строка каждого набора входных данных содержит двоичную строку $$$a$$$ ($$$|a| = n$$$), состоящую только из символов $$$\texttt{0}$$$ и/или $$$\texttt{1}$$$.

Третья строка каждого набора входных данных содержит двоичную строку $$$b$$$ ($$$|b| = n$$$), состоящую только из символов $$$\texttt{0}$$$ и/или $$$\texttt{1}$$$.

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

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

Для каждого набора входных данных выведите минимальное количество операций, необходимое для преобразования $$$a$$$ в $$$b$$$. Если это невозможно, вместо этого выведите $$$-1$$$.

Пример
Входные данные
5
4
0100
0001
4
0100
0010
6
110000
000011
8
10101010
10101010
5
01001
10010
Выходные данные
1
-1
4
0
3
Примечание

В первом наборе входных данных можно выбрать подстроку $$$a[2, 4] = \texttt{100}$$$ и заменить её на $$$\texttt{001}$$$. Это занимает ровно $$$1$$$ операцию.

Во втором наборе входных данных преобразовать $$$a$$$ в $$$b$$$ невозможно, поэтому ответ равен $$$-1$$$.

В третьем наборе входных данных можно сделать следующее по порядку:

  • $$$\texttt{1}$$$$$${\color{blue}{\texttt{100}}}$$$$$$\texttt{00}$$$ $$$\rightarrow$$$ $$$\texttt{1}$$$$$${\color{blue}{\texttt{001}}}$$$$$$\texttt{00}$$$
  • $$$\texttt{100}$$$$$${\color{blue}{\texttt{100}}}$$$ $$$\rightarrow$$$ $$$\texttt{100}$$$$$${\color{blue}{\texttt{001}}}$$$
  • $$${\color{blue}{\texttt{100}}}$$$$$$\texttt{001}$$$ $$$\rightarrow$$$ $$${\color{blue}{\texttt{001}}}$$$$$$\texttt{001}$$$
  • $$$\texttt{00}$$$$$${\color{blue}{\texttt{100}}}$$$$$$\texttt{1}$$$ $$$\rightarrow$$$ $$$\texttt{00}$$$$$${\color{blue}{\texttt{001}}}$$$$$$\texttt{1}$$$

Это занимает $$$4$$$ операции. Можно показать, что $$$4$$$ — минимальный ответ.