马克刚刚购买了一架 $$$n$$$ 灯泡。灯泡的状态可以用二进制字符串 $$$s = s_1s_2\dots s_n$$$ 来描述,其中 $$$s_i=\texttt{1}$$$ 表示第 $$$i$$$ 个灯泡打开,而 $$$s_i=\texttt{0}$$$ 表示第 $$$i$$$ 个灯泡关闭。
不幸的是,灯泡坏了,他可以执行的唯一操作来更改灯泡的状态如下:
- 从 $$$2,3,\dots,n-1$$$ 中选择索引 $$$i$$$,使得 $$$s_{i-1}\ne s_{i+1}$$$。
- 切换 $$$s_i$$$。即,如果 $$$s_i$$$ 为 $$$\texttt{0}$$$,则将 $$$s_i$$$ 设置为 $$$\texttt{1}$$$,反之亦然。
Mark 希望灯泡的状态是另一个二进制字符串 $$$t$$$。帮助马克确定执行此操作的最少操作数。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一行,其中包含 Mark 将 $$$s$$$ 转换为 $$$t$$$ 所需执行的最少操作数。如果没有这样的操作序列,则打印$$$-1$$$。
示例
输入 #1
4 4 0100 0010 4 1010 0100 5 01001 00011 6 000101 010011
输出 #1
2 -1 -1 5
注意
在第一个测试用例中,实现最少操作数的操作序列如下。
- 选择 $$$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$$$和$$$t$$$的第一位数字相同,并且$$$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}$$$。