demon的盗版像素工坊

背景

7unar 把「像素工坊」推荐给了 demon。demon 上网搜了个盗版就装上了。

打开一看，核心玩法倒是一样——屏幕上有一排 $n$ 个像素格子，每个格子要么是黑色块，要么是白色块。

用手指框住连续三个像素，系统就会识别它们的排列模式，帮你一键切换：

• 黑色块 黑色块 白色块 一键变成 白色块 黑色块 黑色块（反过来也行）

• 黑色块 白色块 白色块 一键变成 白色块 白色块 黑色块（反过来也行）

但盗版的设计师比正版心黑得多——关卡目标不只是问你「能不能从初始序列 $a$ 变到目标序列 $b$」，而是要你求出最少需要多少次操作。

如果根本无法变换（盗版免不了有 bug），那就输出 $-1$。

注意：输入中，黑色块用 $0$ 表示，白色块用 $1$ 表示。

题目描述

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

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

• 选择一个子串 001，替换为 100（反过来也行：100 $\to$ 001）

• 选择一个子串 110，替换为 011（反过来也行：011 $\to$ 110）

求将字符串 $a$ 变成字符串 $b$ 所需的最少操作次数。如果无法变换，输出 $-1$。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^{4}$），表示测试数据组数。

每组测试数据：

• 第一行一个整数 $n$（$1 \le n \le 2 \times 10^{5}$），表示字符串长度。

• 第二行一个字符串 $a$（$|a| = n$），由字符 $0$ 和 $1$ 组成。

• 第三行一个字符串 $b$（$|b| = n$），由字符 $0$ 和 $1$ 组成。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^{5}$。

输出格式

对于每组测试数据，输出一个整数，表示最少操作次数。如果无法变换，输出 $-1$。

样例

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

1
-1
4
0
3

样例解释

• 第一组：选择 $a[2 \ldots 4] =$ 100，替换为 001，$1$ 次操作。

• 第二组：无法变换，输出 $-1$。

• 第三组：最少 $4$ 次，过程如下：

  110000 $\to$ 100100 $\to$ 001100 $\to$ 000011

• 第四组：$a = b$，不需要操作，输出 $0$。

• 第五组：最少 $3$ 次操作。

数据范围

• $1 \le t \le 10^{4}$

• $1 \le n \le 2 \times 10^{5}$

• $\sum n \le 2 \times 10^{5}$