G. Yet Yet Another Binary String Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can do the following operation any number of times:

  • Choose an index $$$i$$$ ($$$1 \lt i \lt n$$$), which satisfies $$$a_{i-1} \neq a_{i+1}$$$, then flip $$$a_i$$$. That is, change $$$a_i$$$ to $$$1$$$ if $$$a_i=0$$$, and change $$$a_i$$$ to $$$0$$$ otherwise ($$$a_i=1$$$).

Find the minimum number of operations to change $$$a$$$ to $$$b$$$. If you cannot change $$$a$$$ to $$$b$$$, output $$$-1$$$ instead.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 4 \cdot 10^5$$$), the length of the binary strings $$$a$$$ and $$$b$$$.
  • The second line contains a binary string $$$a$$$ of length $$$n$$$.
  • The third line contains a binary string $$$b$$$ of length $$$n$$$.

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

Output

For each test case, output a single line containing the minimum number of operations to change $$$a$$$ to $$$b$$$. If you can not change $$$a$$$ to $$$b$$$, output $$$-1$$$ instead.

Example
Input
5
3
000
011
3
000
111
3
000
000
4
0010
0100
5
11101
10011
Output
-1
-1
0
2
3
Note

In the first and second test cases, you cannot change $$$a$$$ to $$$b$$$.

In the third test case, $$$a$$$ and $$$b$$$ are already equal, so you don't need to do any operations.

In the fourth test case, you can change $$$a$$$ to $$$b$$$ after the following two operations:

  1. Choose $$$i=2$$$, which satisfies $$$a_{i-1} \neq a_{i+1}$$$, then flip $$$a_2$$$. After that, $$$a=0110$$$;
  2. Choose $$$i=3$$$, which satisfies $$$a_{i-1} \neq a_{i+1}$$$, then flip $$$a_3$$$. After that, $$$a=0100=b$$$.

It can be proven that $$$2$$$ is the minimum number of operations.