该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你两个长度相同的二进制字符串 a 和 b。

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

• 在 a 中选择等于 001 的子串并替换为 100，反之亦然（即 001 → 100 或 100 → 001）。
• 在 a 中选择等于 110 的子串并替换为 011，反之亦然（即 011 → 110 或 110 → 011）。

你的任务是确定将字符串 a 转换为字符串 b 所需的最少操作数。如果无法通过给定操作将 a 转换为 b，则输出 -1。

输入格式

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

接下来是 t 个测试用例的描述：

• 第一行包含一个整数 n（1 ≤ n ≤ 2 × 10^5）——每个字符串的长度。
• 第二行包含一个二进制字符串 a（|a| = n），仅由字符 0 和 1 组成。
• 第三行包含一个二进制字符串 b（|b| = n），仅由字符 0 和 1 组成。

保证所有测试用例中 n 的总和不超过 2 × 10^5。

输出格式

对于每个测试用例，输出将 a 转换为 b 所需的最少操作数。如果不可能，则输出 -1。

示例

输入

text****编辑

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

输出

text****编辑

1
-1
4
0
3

示例说明

第一个测试用例：可以选择子串 a[2,4] = 100 并将其替换为 001，恰好需要 1 次操作。

第二个测试用例：无法将 a 转换为 b，因此答案为 -1。 在第三个测试案例中，我们可以依次进行以下操作： 初始状态：110000 第1次操作，将第2到第4位的 100 替换为 001： 110000 -> 100100 第2次操作，将第4到第6位的 100 替换为 001： 100100 -> 100001 第3次操作，将第1到第3位的 100 替换为 001： 100001 -> 001001 第4次操作，将第3到第5位的 100 替换为 001： 001001 -> 000011 共需要 4 次操作。可以证明 4 是最小值。

共需要 4 次操作，可以证明 4 是最小值。