CF1705D.Mark and Lightbulbs

Mark has just purchased a rack of $n$ lightbulbs. The state of the lightbulbs can be described with binary string $s = s_1s_2\dots s_n$, where $s_i=\texttt{1}$ means that the $i$-th lightbulb is turned on, while $s_i=\texttt{0}$ means that the $i$-th lightbulb is turned off.

Unfortunately, the lightbulbs are broken, and the only operation he can perform to change the state of the lightbulbs is the following:

• Select an index $i$ from $2,3,\dots,n-1$ such that $s_{i-1}\ne s_{i+1}$.
• Toggle $s_i$. Namely, if $s_i$ is $\texttt{0}$, set $s_i$ to $\texttt{1}$ or vice versa.

Mark wants the state of the lightbulbs to be another binary string $t$. Help Mark determine the minimum number of operations to do so.

马克刚刚购买了一排 $n$ 个灯泡。灯泡的状态可以用一个二进制字符串 $s = s_1s_2\dots s_n$ 来描述，其中 $s_i=\texttt{1}$ 表示第 $i$ 个灯泡处于开启状态，而 $s_i=\texttt{0}$ 表示第 $i$ 个灯泡处于关闭状态。

不幸的是，这些灯泡损坏了，马克唯一能执行的、用于改变灯泡状态的操作如下：

• 选择一个下标 $i$，满足 $i \in \{2,3,\dots,n-1\}$ 且 $s_{i-1}\ne s_{i+1}$；
• 翻转 $s_i$ 的值（即若 $s_i$ 为 $\texttt{0}$，则将其改为 $\texttt{1}$；若为 $\texttt{1}$，则改为 $\texttt{0}$）。

马克希望将灯泡的状态变为另一个二进制字符串 $t$。请帮助马克确定达成目标所需的最少操作次数。

The first line of the input contains a single integer $q$ ($1\leq q\leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($3\leq n\leq 2\cdot 10^5$) — the number of lightbulbs.

The second line of each test case contains a binary string $s$ of length $n$ — the initial state of the lightbulbs.

The third line of each test case contains a binary string $t$ of length $n$ — the final state of the lightbulbs.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

输入的第一行包含一个整数 $q$（$1\leq q\leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3\leq n\leq 2\cdot 10^5$），表示灯泡的数量。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，表示灯泡的初始状态。

每个测试用例的第三行包含一个长度为 $n$ 的二进制字符串 $t$，表示灯泡的目标状态。

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

For each test case, print a line containing the minimum number of operations Mark needs to perform to transform $s$ to $t$. If there is no such sequence of operations, print $-1$.

对于每个测试用例，输出一行，包含 Mark 将 $s$ 变换为 $t$ 所需的最少操作次数。如果不存在这样的操作序列，则输出 $-1$。

In the first test case, one sequence of operations that achieves the minimum number of operations is the following.

• Select $i=3$, changing $\texttt{01}\color{red}{\texttt{0}}\texttt{0}$ to $\texttt{01}\color{red}{\texttt{1}}\texttt{0}$.
• Select $i=2$, changing $\texttt{0}\color{red}{\texttt{1}}\texttt{10}$ to $\texttt{0}\color{red}{\texttt{0}}\texttt{10}$.

In the second test case, there is no sequence of operations because one cannot change the first digit or the last digit of $s$.

In the third test case, even though the first digits of $s$ and $t$ are the same and the last digits of $s$ and $t$ are the same, it can be shown that there is no sequence of operations that satisfies the condition.

In the fourth test case, one sequence that achieves the minimum number of operations is the following:

• Select $i=3$, changing $\texttt{00}\color{red}{\texttt{0}}\texttt{101}$ to $\texttt{00}\color{red}{\texttt{1}}\texttt{101}$.
• Select $i=2$, changing $\texttt{0}\color{red}{\texttt{0}}\texttt{1101}$ to $\texttt{0}\color{red}{\texttt{1}}\texttt{1101}$.
• Select $i=4$, changing $\texttt{011}\color{red}{\texttt{1}}\texttt{01}$ to $\texttt{011}\color{red}{\texttt{0}}\texttt{01}$.
• Select $i=5$, changing $\texttt{0110}\color{red}{\texttt{0}}\texttt{1}$ to $\texttt{0110}\color{red}{\texttt{1}}\texttt{1}$.
• Select $i=3$, changing $\texttt{01}\color{red}{\texttt{1}}\texttt{011}$ to $\texttt{01}\color{red}{\texttt{0}}\texttt{011}$.

在第一个测试用例中，一种能够达到最少操作次数的操作序列如下：

• 选择 $i=3$，将 $\texttt{01}\color{red}{\texttt{0}}\texttt{0}$ 变为 $\texttt{01}\color{red}{\texttt{1}}\texttt{0}$。
• 选择 $i=2$，将 $\texttt{0}\color{red}{\texttt{1}}\texttt{10}$ 变为 $\texttt{0}\color{red}{\texttt{0}}\texttt{10}$。

在第二个测试用例中，不存在可行的操作序列，因为无法修改字符串 $s$ 的第一位或最后一位。

在第三个测试用例中，尽管 $s$ 和 $t$ 的第一位相同、最后一位也相同，但可以证明并不存在满足条件的操作序列。

在第四个测试用例中，一种能够达到最少操作次数的操作序列如下：

• 选择 $i=3$，将 $\texttt{00}\color{red}{\texttt{0}}\texttt{101}$ 变为 $\texttt{00}\color{red}{\texttt{1}}\texttt{101}$。
• 选择 $i=2$，将 $\texttt{0}\color{red}{\texttt{0}}\texttt{1101}$ 变为 $\texttt{0}\color{red}{\texttt{1}}\texttt{1101}$。
• 选择 $i=4$，将 $\texttt{011}\color{red}{\texttt{1}}\texttt{01}$ 变为 $\texttt{011}\color{red}{\texttt{0}}\texttt{01}$。
• 选择 $i=5$，将 $\texttt{0110}\color{red}{\texttt{0}}\texttt{1}$ 变为 $\texttt{0110}\color{red}{\texttt{1}}\texttt{1}$。
• 选择 $i=3$，将 $\texttt{01}\color{red}{\texttt{1}}\texttt{011}$ 变为 $\texttt{01}\color{red}{\texttt{0}}\texttt{011}$。