这是该问题的简单版本。两个版本之间的区别在于，在此版本中，字符串 $t$ 仅由 '0' 和 '1' 组成。只有当你解决了该问题的所有版本后，才能进行 Hack。

Kevin 有一个长度为 $n$ 的 01 字符串 $s$。Kevin 可以进行以下操作：

• 选择 $s$ 的两个相邻块并交换它们。

一个“块”是指由相同字符组成的最大连续子串*。形式化地，记 $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$ 的两个块 $s[l_1, r_1]$ 和 $s[l_2, r_2]$。

例如，如果 $s = \texttt{000 11 00 111}$，Kevin 可以选择两个块 $s[4, 5]$ 和 $s[6, 7]$ 并交换它们，从而将 $s$ 变换为 $\texttt{000 00 11 111}$。

给定一个长度为 $n$ 且由 '0'、'1' 和 '?' 组成的字符串 $t$。Kevin 想要确定最少需要进行多少次操作，使得对于任意索引 $i$ ($1 \le i \le n$)，如果 $t_i \neq \text{'?'}$，则 $s_i = t_i$。如果无法做到，则输出 $-1$。

* 如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干个（可能是零个或全部）字符以及从末尾删除若干个（可能是零个或全部）字符来获得，则称 $a$ 是 $b$ 的子串。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。随后是测试用例的描述。

每个测试用例的第一行包含一个由 '0' 和 '1' 组成的字符串 $s$。

每个测试用例的第二行包含一个由 '0' 和 '1' 组成的字符串 $t$。

保证 $s$ 和 $t$ 的长度相同。

保证所有测试用例中 $s$ 的长度之和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数——所需的最少操作次数。如果无法做到，则输出 $-1$。

样例

输入 1

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

输出 1

1
3
1
-1
-1
-1

说明

在第一个测试用例中，一种可行的方法已在题目描述中给出。

在第二个测试用例中，一种可行的方法可以是：

• 交换块 $[2, 2]$ 和 $[3, 3]$，$s$ 将变为 $001101$。
• 交换块 $[3, 4]$ 和 $[5, 5]$，$s$ 将变为 $000111$。
• 交换块 $[1, 3]$ 和 $[4, 6]$，$s$ 将变为 $111000$。