これはこの問題のハードバージョンです。このバージョンとイージーバージョンの違いは、文字列 $t$ が '0'、'1'、'?' から構成される点です。この問題のすべてのバージョンを解いた場合にのみ、ハックを行うことができます。

Kevin は長さ $n$ の二進文字列 $s$ を持っています。Kevin は以下の操作を行うことができます。

• $s$ の隣接する2つのブロックを選び、それらを入れ替える。

ブロックとは、同一の文字からなる極大な部分文字列$^*$のことです。形式的には、$s[l, r]$ を部分文字列 $s_l s_{l+1} \dots s_r$ と表します。ブロックとは、以下の条件を満たす $s[l, r]$ です。

• $l = 1$ または $s_l \neq s_{l-1}$。
• $s_l = s_{l+1} = \dots = s_r$。
• $r = n$ または $s_r \neq s_{r+1}$。

隣接するブロックとは、$r_1 + 1 = l_2$ を満たす2つのブロック $s[l_1, r_1]$ と $s[l_2, r_2]$ のことです。

例えば、$s = 000 11 00 111$ の場合、Kevin は2つのブロック $s[4, 5]$ と $s[6, 7]$ を選んで入れ替えることができ、文字列 $s$ は $000 00 11 111$ に変化します。

'0'、'1'、'?' からなる長さ $n$ の文字列 $t$ が与えられたとき、任意のインデックス $i$ ($1 \le i \le n$) について、$t_i \neq \text{'?'}$ ならば $s_i = t_i$ となるようにするために必要な最小の操作回数を求めてください。不可能な場合は $-1$ を出力してください。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。 続いて各テストケースの説明が続きます。 各テストケースの1行目には '0' と '1' からなる文字列 $s$ が含まれます。 各テストケースの2行目には '0'、'1'、'?' からなる文字列 $t$ が含まれます。 $s$ と $t$ の長さは等しいことが保証されています。 すべてのテストケースにおける $s$ の長さの合計は $4 \cdot 10^5$ を超えないことが保証されています。

出力

各テストケースについて、必要な最小の操作回数を整数で出力してください。不可能な場合は $-1$ を出力してください。

$^*$ 文字列 $a$ が文字列 $b$ の部分文字列であるとは、$b$ の先頭からいくつかの文字（0個またはすべてでもよい）と末尾からいくつかの文字（0個またはすべてでもよい）を削除することで $a$ が得られることを指します。

入出力例

入力 1

6
0001100111
0000011111
010101
111000
0101
0110
0101
1010
011001
001110
0
1

出力 1

1
3
1
-1
-1
-1

入力 2

6
010101
?0?0??
0101
?0?0
11100101
????????
11100101
???11?1?
1000100011
?11?000?0?
10101
?1011

出力 2

2
-1
0
2
2
-1

注記

最初の例の最初のテストケースでは、問題文中で示された方法が可能です。 最初の例の2番目のテストケースでは、考えられる方法の一つは以下の通りです。

• ブロック $[2, 2]$ と $[3, 3]$ を入れ替えると、$s$ は $001101$ になります。
• ブロック $[3, 4]$ と $[5, 5]$ を入れ替えると、$s$ は $000111$ になります。
• ブロック $[1, 3]$ と $[4, 6]$ を入れ替えると、$s$ は $111000$ になります。

2番目の例の最初のテストケースでは、考えられる方法の一つは以下の通りです。

• ブロック $[1, 1]$ と $[2, 2]$ を入れ替えると、$s$ は $100101$ になります。
• ブロック $[4, 4]$ と $[5, 5]$ を入れ替えると、$s$ は $100011$ になります。