这是本题的困难版本。两个版本之间的区别在于，在此版本中，字符串 $t$ 由 '0'、'1' 和 '?' 组成。只有当你解决了本题的所有版本时，才能进行 Hack。

Kevin 有一个长度为 $n$ 的二进制字符串 $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 = 0001100111$，Kevin 可以选择两个块 $s[4, 5]$ 和 $s[6, 7]$ 并交换它们，将 $s$ 转化为 $0000011111$。

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

输入格式

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

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

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

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

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

输出格式

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

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

样例

输入样例 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]$ 和 $[3, 3]$，$s$ 将变为 $001101$。
• 交换块 $[3, 4]$ 和 $[5, 5]$，$s$ 将变为 $000111$。
• 交换块 $[1, 3]$ 和 $[4, 6]$，$s$ 将变为 $111000$。

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

• 交换块 $[1, 1]$ 和 $[2, 2]$，$s$ 将变为 $100101$。
• 交换块 $[4, 4]$ 和 $[5, 5]$，$s$ 将变为 $100011$。