これはこの問題のイージーバージョンです。このバージョンとハードバージョンの違いは、このバージョンでは文字列 $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$ が与えられます。Kevin は、任意のインデックス $i$ ($1 \le i \le n$) について、$t_i \neq$ '?' ならば $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番目のテストケースでは、一つの可能な手順は以下の通りです。

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