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

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии строка $$$t$$$ состоит из «0», «1» и «?». Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У Кевина есть бинарная строка $$$s$$$ длины $$$n$$$. Кевин может выполнять следующую операцию:

  • Выбрать два соседних блока строки $$$s$$$ и поменять их местами.

Блок — это максимальная по включению подстрока$$$^{\text{∗}}$$$ из одинаковых символов. Формально, обозначим подстроку $$$s_l s_{l+1} \ldots s_r$$$ как $$$s[l,r]$$$. Тогда $$$s[l,r]$$$ является блоком, если выполняются все условия:

  • $$$l=1$$$ или $$$s_l\not=s_{l-1}$$$.
  • $$$s_l=s_{l+1} = \ldots = s_{r}$$$.
  • $$$r=n$$$ или $$$s_r\not=s_{r+1}$$$.

Соседними блоками являются два блока $$$s[l_1,r_1]$$$ и $$$s[l_2,r_2]$$$, для которых $$$r_1+1=l_2$$$.

Например, если $$$s=\mathtt{000}\,\mathbf{11}\,\mathbf{00}\,\mathtt{111}$$$, Кевин может выбрать два блока $$$s[4,5]$$$ и $$$s[6,7]$$$ и поменять их местами, преобразовав $$$s$$$ в $$$\mathtt{000}\,\mathbf{00}\,\mathbf{11}\,\mathtt{111}$$$.

Дана строка $$$t$$$ длины $$$n$$$, состоящая из символов «0», «1» и «?». Кевин хочет определить минимальное количество операций, необходимых для получения строки, для которой выполняется следующее условие: для любого индекса $$$i$$$ ($$$1\le i\le n$$$), если $$$t_i\not=$$$ '?', то $$$s_i=t_i$$$. Если это невозможно, выведите $$$-1$$$.

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

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

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

Первая строка каждого набора входных данных содержит строку $$$s$$$, состоящую из «0» и «1».

Вторая строка каждого набора входных данных содержит строку $$$t$$$, состоящую из «0», «1» и «?».

Гарантируется, что $$$s$$$ и $$$t$$$ имеют одинаковую длину.

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

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

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

Примеры
Входные данные
6
0001100111
0000011111
010101
111000
0101
0110
0101
1010
011001
001110
0
1
Выходные данные
1
3
1
-1
-1
-1
Входные данные
6
010101
?0?0??
0101
?0?0
11100101
????????
11100101
???11?1?
1000100011
?11?000?0?
10101
?1011
Выходные данные
2
-1
0
2
2
-1
Примечание

В первом наборе первого примера возможная последовательность операций приведена в условии.

Во втором наборе первого примера можно применить такую последовательность операций:

  • Переставить блоки $$$[2, 2], [3, 3]$$$: $$$s$$$ станет $$$\mathtt{001101}$$$.
  • Переставить блоки $$$[3, 4], [5, 5]$$$: $$$s$$$ станет $$$\mathtt{000111}$$$.
  • Переставить блоки $$$[1, 3], [4, 6]$$$: $$$s$$$ станет $$$\mathtt{111000}$$$.

В первом наборе второго примера можно применить такую последовательность операций:

  • Переставить блоки $$$[1, 1], [2, 2]$$$: $$$s$$$ станет $$$\mathtt{100101}$$$.
  • Переставить блоки $$$[4, 4], [5, 5]$$$: $$$s$$$ станет $$$\mathtt{100011}$$$.