Problem Statement

You are given strings $A$ and $B$ of length $N$ consisting of 0 and 1. Let $A_i$ denote the $i$-th character of $A$.

You can perform the following operation any number of times, possibly zero.

• Choose an integer $i\ (2 \leq i \leq N-1)$ satisfying $A_{i-1} = A_{i+1}$, and flip $A_i$ (change 1 to 0 or 0 to 1).

Determine whether you can make $A$ equal to $B$ by repeating the operation, and if so, find the minimum number of operations required.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $3 \leq N \leq 10^6$
• $A$ and $B$ are strings of length $N$ consisting of 0 and 1.
• $T$ and $N$ are integers.
• The sum of $N$ over all test cases is at most $10^6$.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A
B

Output

Output the answers for $\mathrm{case}_1, \mathrm{case}_2, \ldots, \mathrm{case}_T$ in the following format.

If it is impossible to make $A$ equal to $B$, print -1.

If it is possible, print the minimum number of operations required.