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 and T of lengths N and M respectively. We can perform the following operations on string S.

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

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

------ Input Format ------ 

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

------ Output Format ------ 

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

------ Constraints ------ 

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

----- Sample Input 1 ------ 
2
3 3
101
000
4 3
0100
000

----- Sample Output 1 ------ 
2
-1

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

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

Difficulty: VERY_HARD
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []
gp = []
ans = []
f = 0
w = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def dfs(i, prod, rem, n):
	if rem == 0:
		while i < len(n):
			prod *= int(n[i])
			i += 1
		return prod
	if i == len(n):
		return prod
	mx = 0
	for j in range(9 - int(n[i])):
		mx = max(dfs(i + 1, (int(n[i]) + min(j, rem)) * prod, rem - min(j, rem), n), mx)
	return mx

def hnbhai(tc):
	(n, m) = sd()
	s = sa()
	t = sa()
	if m < n:
		print(-1)
		return
	diff = m - n
	mn = float('inf')
	for i in range(diff + 1):
		seq = []
		if i != 0:
			seq.append(i - 1)
		else:
			seq.append(float('-inf'))
		for j in range(n):
			if s[j] != t[j + i]:
				seq.append(j + i)
		if diff - i != 0:
			seq.append(n + i)
		else:
			seq.append(float('inf'))
		if len(seq) == 2:
			print(diff)
			return
		j = 1
		dp = [[float('inf'), float('inf')] for _ in range(len(seq) + 4)]
		dp[0][0] = 0
		dp[0][1] = 0
		while j < len(seq) - 1:
			dp[j][0] = min(dp[j][0], dp[j - 1][1] + seq[j] - seq[j - 1])
			dp[j][1] = dp[j - 1][0]
			j += 1
		mn = min(mn, diff + dp[len(seq) - 2][0], diff + dp[len(seq) - 2][1] + seq[len(seq) - 1] - seq[len(seq) - 2])
	if mn == float('inf'):
		print(-1)
		return
	print(mn)
	return
for _ in range(sb()):
	hnbhai(_ + 1)


def mini(s, t):
	l = len(s)
	ops = 0
	for i in range(l - 1):
		if s[i] != t[i]:
			s[i] = 1 - s[i]
			s[i + 1] = 1 - s[i + 1]
			ops += 1
	return ops
Test = int(input())
for test in range(Test):
	temp = input().split()
	ops = []
	(n, m) = (int(temp[0]), int(temp[1]))
	S_str = input()
	T_str = input()
	s = list(S_str)
	t = list(T_str)
	S = [int(x) for x in s]
	T = [int(x) for x in t]
	if len(S) > len(T):
		pass
	else:
		for i in range(len(T) - len(S) + 1):
			T_temp = T[i:i + len(S)]
			if (sum(T_temp) - sum(S)) % 2 != 0:
				if len(S) == len(T):
					pass
				else:
					temp = [1 + mini([1 - S[0]] + S[1:], T_temp), 1 + mini(S[:-1] + [1 - S[-1]], T_temp)]
					ops = ops + temp
			else:
				ops.append(mini(S[:], T_temp))
				if len(T) > len(S) + 1:
					ops.append(2 + mini([1 - S[0]] + S[1:-1] + [1 - S[-1]], T_temp))
	if ops == []:
		print('-1')
	else:
		ans = min(ops) + len(T) - len(S)
		print(ans)


def solve(a, b):
	n = len(a)
	(i, count) = (0, 0)
	while i < n:
		while i < n and a[i] == b[i]:
			i += 1
		if i == n:
			return count
		i += 1
		while i < n and a[i] == b[i]:
			i += 1
			count += 1
		if i == n:
			return float('inf')
		(count, i) = (count + 1, i + 1)
	return count

def answer():
	if n > m:
		return -1
	ans = float('inf')
	for i in range(m - n + 1):
		x = a[:]
		y = b[i:i + n]
		ans = min(ans, solve(x, y))
		if i > 0:
			x = a[:]
			y = b[i - 1] + b[i:i + n]
			if b[i - 1] == '1':
				ans = min(ans, solve('0' + x, y))
			else:
				ans = min(ans, solve('1' + x, y))
		if i < m - n:
			ans = min(ans, solve(a[:] + ('0' if b[i + n] == '1' else '1'), b[i:i + n] + b[i + n]))
		if i and i != m - n:
			x = a[:]
			y = b[i - 1] + b[i:i + n] + b[i + n]
			front = '0' if b[i - 1] == '1' else '1'
			back = '0' if b[i + n] == '1' else '1'
			ans = min(ans, solve(front + x + back, y))
	return -1 if ans == float('inf') else ans + (m - n)
for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = input().strip()
	b = input().strip()
	print(answer())


INF = float('inf')

def count(s, t):
	s = s.copy()
	t = t.copy()
	if len(s) != len(t):
		return INF
	n = len(s)
	c = 0
	for i in range(n):
		if s[i] != t[i]:
			if i + 1 >= n:
				return INF
			c += 1
			s[i] ^= 1
			s[i + 1] ^= 1
	return c

def solve(s, t, beg, end):
	s = s.copy()
	t = t.copy()
	tot = beg + end
	t = t[beg:]
	if end != 0:
		t = t[:-end]
	if beg == end == 0:
		return count(s, t) + tot
	elif end == 0:
		c1 = count(s, t)
		s[0] ^= 1
		c2 = count(s, t) + 1
		return min(c1, c2) + tot
	elif beg == 0:
		c1 = count(s, t)
		s[-1] ^= 1
		c2 = count(s, t) + 1
		return min(c1, c2) + tot
	else:
		c1 = count(s, t)
		s[0] ^= 1
		c2 = count(s, t) + 1
		s[-1] ^= 1
		c3 = count(s, t) + 2
		s[0] ^= 1
		c4 = count(s, t) + 1
		return min(c1, c2, c3, c4) + tot
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = list(map(int, input().strip()))
	t = list(map(int, input().strip()))
	if n > m:
		print(-1)
		continue
	elif m == n:
		x = solve(s, t, 0, 0)
		print(x if x != INF else -1)
	else:
		tot = m - n
		mini = INF
		for i in range(tot + 1):
			mini = min(mini, solve(s, t, i, tot - i))
		if mini == INF:
			print(-1)
		else:
			print(mini)