The One Where Joey Dates Rachel

 Everybody is sad, most of all Monica as Chandler must spend Christmas and New Years in Tulsa, where his staff is all depressed they can't be with their families. He arranged for the head office to send a bonus, but even that's another bummer: donations in their name to the New York ballet. Chandler sends a message to the head office in the form of a binary code, which somehow gets changed on the way.

Chef is given two binary strings S$S$ and T$T$ of lengths N$N$ and M$M$ respectively. We can perform the following operations on string S$S$.

• Select two adjacent characters of the string S$S$ and flip these two characters. ( Flipping the character 1$1$ is equivalent to replacing the character 1$1$ with 0$0$, and vice-versa )
• Add a character, either 0$0$ or 1$1$ to any of the ends ( either the front or the back ) of the string S$S$.

Find the minimum number of operations needed to convert S$S$ to T$T$. If it is impossible to convert S$S$ to T$T$, print -1.

Input Format

• First line will contain T$T$, number of testcases. Then the testcases follow.
• First line of each testcase contains of a single line of input, two integers N,M$N,M$.
• Second line of each testcase contains a binary string S$S$.
• Third line of each testcase contains a binary string T$T$.

Output Format

For each testcase, output in a single line the minimum number of operations needed to convert S$S$ to T$T$. If it is impossible to convert, print -1.

Constraints

• 1≤T≤20$1\le T\le 20$
• 1≤N,M≤1000$1\le N,M\le 1000$
• S,T$S,T$ contain 0,1$0,1$ only.

Sample Input 1 

2
3 3
101
000
4 3
0100
000

Sample Output 1 

2
-1

Explanation

Test case 1: Flip the first two bits in one move and second two bits in second move. 101$101$ →$\to$ 011$011$ →$\to$ 000$000$.

Test case 2: It is impossible to convert S$S$ to T$T$ using any sequence of moves.

Click here