题目描述

这是该问题的困难版本。在这个版本中，你需要求出将字符串 $a$ 转换为字符串 $b$ 的最少操作次数。

给定两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。

你可以执行以下任意操作：

• 选定 $a$ 中等于 001 的子串并将其替换为 100，反之亦然（即 001 $\to$ 100 或 100 $\to$ 001）。
• 选定 $a$ 中等于 110 的子串并将其替换为 011，反之亦然（即 011 $\to$ 110 或 110 $\to$ 011）。

你的任务是求出将字符串 $a$ 转换为字符串 $b$ 所需的最少操作次数。如果无法使用上述操作将 $a$ 转换为 $b$，请输出 -1。

字符串的子串是指通过从原字符串的开头和/或结尾删除若干（可能为零个或全部）个字符所得到的连续字符串片段。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 字符串的长度。
• 第二行包含一个长度为 $n$ 的二进制字符串 $a$，仅由字符 0 和 1 组成。
• 第三行包含一个长度为 $n$ 的二进制字符串 $b$，仅由字符 0 和 1 组成。

输出格式

对于每个测试用例，输出一行一个整数，表示将字符串 $a$ 转换为字符串 $b$ 所需的最少操作次数。如果无法转换，输出 -1。

样例输入 1

5
4
0100
0001
4
0100
0010
6
110000
000011
8
10101010
10101010
5
01001
10010

样例输出 1

1
-1
4
0
3

说明

样例解释

• 在第一个测试用例中，我们可以选择子串 $a[2\dots4] = \text{"100"}$ 并将其替换为 $\text{"001"}$。这恰好需要 $1$ 次操作。
• 在第二个测试用例中，无法将 $a$ 转换为 $b$，因此答案为 -1。
• 在第三个测试用例中，我们可以依次进行如下操作： 110000 $\to$ 100100 100100 $\to$ 100001 100001 $\to$ 001001 001001 $\to$ 000011 这总共需要 $4$ 次操作。可以证明 $4$ 次是最少的所需操作次数。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le n \le 2 \times 10^5$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 保证所有的输入字符串仅由 0 和 1 组成。