You have two binary strings A and B, both of length N. You have to merge both the binary strings to form a new binary string C of length 2 \cdot N. The relative order of characters in the original binary strings A and B should not change in the binary string C.

For example, if A = {\color{blue}01011} and B = {\color{red}10100}, one possible way to merge them to form C is: C = {\color{blue}0}{\color{red}1}{\color{red}0}{\color{blue}1}{\color{red}1}{\color{blue}0}{\color{blue}1}{\color{blue}1}{\color{red}0}{\color{red}0}.

Minimize the number of inversions in the merged binary string C.

As a reminder, a pair of indices (i, j) is an inversion for binary string C if and only if 1 ≤ i < j ≤ |C|, C_{i} = 1 and C_{j} = 0.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N — the length of the binary strings A and B.
- The second line of each test case contains the binary string A.
- The third line of each test case contains the binary string B.

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

For each test case, output a single line containing the minimum number of inversions in the merged binary string C.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 1000$
- It is guaranteed that the sum of $N$ over all test cases does not exceed $2000$.
$|A| = |B| = N$
$A$ and $B$ are binary strings, i.e, contain only $0$ and $1$.

----- Sample Input 1 ------ 
3
4
1010
0101
5
10010
11001
5
00001
11110

----- Sample Output 1 ------ 
6
12
4

----- explanation 1 ------ 
Test Case $1$: $A = {\color{blue}1010}$ and $B = {\color{red}0101}$. One optimal $C$ is ${\color{red}0}{\color{blue}1}{\color{blue}0}{\color{red}1}{\color{red}0}{\color{blue}1}{\color{blue}0}{\color{red}1}$. The $6$ inversions in this $C$ are $\{(2, 3), (2, 5), (2, 7), (4, 5), (4, 7), (6, 7)\}$.

Test Case $2$: $A = {\color{blue}10010}$ and $B = {\color{red}11001}$. One optimal $C$ is ${\color{blue}1}{\color{blue}0}{\color{blue}0}{\color{red}1}{\color{red}1}{\color{red}0}{\color{red}0}{\color{blue}1}{\color{blue}0}{\color{red}1}$.

Test Case $3$: $A = {\color{blue}00001}$ and $B = {\color{red}11110}$. One optimal $C$ is ${\color{blue}0}{\color{blue}0}{\color{blue}0}{\color{blue}0}{\color{red}1}{\color{red}1}{\color{red}1}{\color{red}1}{\color{red}0}{\color{blue}1}$.

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from functools import lru_cache
from sys import setrecursionlimit, stdin
setrecursionlimit(10 ** 7)
input = stdin.readline
t = int(input())

def solve(N, A, B):

	@lru_cache(None)
	def go(i, j, zeros):
		if i == -1 and j == -1:
			return 0
		tmpi = 2 ** 31
		tmpj = 2 ** 31
		if i >= 0:
			if A[i] == '1':
				tmpi = go(i - 1, j, zeros) + zeros
			else:
				tmpi = go(i - 1, j, zeros + 1)
		if j >= 0:
			if B[j] == '1':
				tmpj = go(i, j - 1, zeros) + zeros
			else:
				tmpj = go(i, j - 1, zeros + 1)
		if tmpj < tmpi:
			return tmpj
		else:
			return tmpi
	print(go(N - 1, N - 1, 0))
while t:
	N = int(input())
	A = input()
	B = input()
	solve(N, A, B)
	t -= 1


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	a = '!' + input()
	b = '!' + input()
	dp = [[0 for x in range(n + 1)] for y in range(n + 1)]
	num_1s_a = [0] * (n + 1)
	num_1s_b = [0] * (n + 1)
	for i in range(1, n + 1):
		num_1s_a[i] = num_1s_a[i - 1] + (a[i] == '1')
		num_1s_b[i] = num_1s_b[i - 1] + (b[i] == '1')
	for i in range(1, n + 1):
		dp[i][0] = dp[i - 1][0]
		if a[i] == '0':
			dp[i][0] += num_1s_a[i - 1]
		dp[0][i] = dp[0][i - 1]
		if b[i] == '0':
			dp[0][i] += num_1s_b[i - 1]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if a[i] == '0':
				dp[i][j] = dp[i - 1][j] + num_1s_a[i - 1] + num_1s_b[j]
			else:
				dp[i][j] = dp[i - 1][j]
			if b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i][j - 1] + num_1s_a[i] + num_1s_b[j - 1])
			else:
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
	print(dp[n][n])


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	INF = float('inf')
	dp = [[INF for j in range(n + 1)] for k in range(n + 1)]
	prea = [0 for j in range(n + 1)]
	preb = [0 for j in range(n + 1)]
	dp[0][0] = 0
	for j in range(1, n + 1):
		prea[j] = prea[j - 1]
		if a[j - 1] == '1':
			prea[j] += 1
	for j in range(1, n + 1):
		preb[j] = preb[j - 1]
		if b[j - 1] == '1':
			preb[j] += 1
	for j in range(1, n + 1):
		dp[0][j] = dp[0][j - 1]
		if a[j - 1] == '0':
			dp[0][j] += prea[j]
	for j in range(1, n + 1):
		dp[j][0] = dp[j - 1][0]
		if b[j - 1] == '0':
			dp[j][0] += preb[j]
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			op1 = dp[j - 1][k]
			if b[j - 1] == '0':
				op1 += prea[k] + preb[j]
			op2 = dp[j][k - 1]
			if a[k - 1] == '0':
				op2 += preb[j] + prea[k]
			dp[j][k] = min(op1, op2)
	print(dp[-1][-1])


for _ in range(int(input())):
	n = int(input())
	a = '#' + input()
	b = '#' + input()
	m = n
	ps = [0] * (n + 1)
	pt = [0] * (n + 1)
	ps[0] = 1 if a[0] == '1' else 0
	pt[0] = 1 if b[0] == '1' else 0
	for i in range(1, n + 1):
		ps[i] = ps[i - 1] + 1 if a[i] == '1' else ps[i - 1]
	for i in range(1, n + 1):
		pt[i] = pt[i - 1] + 1 if b[i] == '1' else pt[i - 1]
	dp = [[0] * (n + 1) for i in range(m + 1)]
	dp[0][0] = 0
	for i in range(1, n + 1):
		dp[i][0] = dp[i - 1][0]
		if a[i] == '0':
			dp[i][0] += ps[i - 1]
	for j in range(1, n + 1):
		dp[0][j] = dp[0][j - 1]
		if b[j] == '0':
			dp[0][j] += pt[j - 1]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if a[i] == '0':
				dp[i][j] = dp[i - 1][j] + ps[i - 1] + pt[j]
			else:
				dp[i][j] = dp[i - 1][j]
			if b[j] == '0':
				dp[i][j] = min(dp[i][j - 1] + ps[i] + pt[j - 1], dp[i][j])
			else:
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
	print(dp[n][n])


for t in range(int(input())):
	N = int(input())
	A = str(input())
	B = str(input())
	sufA = [0]
	sufB = [0]
	for i in range(N - 1, -1, -1):
		if A[i] == '0':
			sufA.append(sufA[-1] + 1)
		else:
			sufA.append(sufA[-1])
		if B[i] == '0':
			sufB.append(sufB[-1] + 1)
		else:
			sufB.append(sufB[-1])
	sufB.reverse()
	sufA.reverse()
	dp = []
	from math import inf
	for i in range(N + 1):
		dp.append([inf] * (N + 1))
	dp[0][0] = 0
	for j in range(N + 1):
		for i in range(N + 1):
			if j < N:
				if B[j] == '0':
					dp[i][j + 1] = min(dp[i][j + 1], dp[i][j])
				else:
					dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + sufA[i] + sufB[j])
			if i < N:
				if A[i] == '0':
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
				else:
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + sufA[i] + sufB[j])
	print(dp[N][N])


from functools import lru_cache
from itertools import count
import sys, io, os
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
flush = lambda : sys.stdout.flush()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	n = cin()
	A = cis()
	B = cis()
	Map = {}

	def dfs(i, j, onecount):
		if i >= n and j >= n:
			return 0
		if (i, j) in Map:
			return Map[i, j]
		count1 = float('inf')
		if i < n:
			caseA = 0
			if A[i] == '1':
				caseA = 1
			forA = 0
			if A[i] == '0':
				forA += onecount
			count1 = min(count1, forA + dfs(i + 1, j, onecount + caseA))
		if j < n:
			forB = 0
			if B[j] == '0':
				forB += onecount
			caseB = 0
			if B[j] == '1':
				caseB = 1
			count1 = min(count1, forB + dfs(i, j + 1, onecount + caseB))
		Map[i, j] = count1
		return count1
	print(dfs(0, 0, 0))
	return
for _ in range(test_case):
	ans()


from sys import stdin
input = stdin.readline

def solve(A, B, N):
	countA0 = [0] * (N + 1)
	countB0 = [0] * (N + 1)
	for i in reversed(range(N)):
		countA0[i] = countA0[i + 1] + (1 if A[i] == '0' else 0)
		countB0[i] = countB0[i + 1] + (1 if B[i] == '0' else 0)
	inversions = [[None] * (N + 1) for i in range(N + 1)]
	inversions[N][N] = 0
	for i in reversed(range(N)):
		inversions[i][N] = (1 if A[i] == '1' else 0) * countA0[i + 1] + inversions[i + 1][N]
		inversions[N][i] = (1 if B[i] == '1' else 0) * countB0[i + 1] + inversions[N][i + 1]
	for i in reversed(range(N)):
		for j in reversed(range(N)):
			inv1 = (1 if A[i] == '1' else 0) * (countA0[i + 1] + countB0[j]) + inversions[i + 1][j]
			inv2 = (1 if B[j] == '1' else 0) * (countA0[i] + countB0[j + 1]) + inversions[i][j + 1]
			inversions[i][j] = min(inv1, inv2)
	return inversions[0][0]
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = input().strip()
	B = input().strip()
	print(solve(A, B, N))


for _ in range(int(input())):
	N = int(input())
	A = input()
	B = input()
	oneCountA = []
	for i in range(len(A)):
		if i == 0:
			oneCountA.append(int(A[i]))
		else:
			oneCountA.append(int(A[i]) + oneCountA[i - 1])
	oneCountB = []
	for i in range(len(B)):
		if i == 0:
			oneCountB.append(int(B[i]))
		else:
			oneCountB.append(int(B[i]) + oneCountB[i - 1])
	dp = [[0 for i in range(N + 1)] for i in range(N + 1)]
	for i in range(N + 1):
		for j in range(N + 1):
			if i == 0 and j == 0:
				dp[i][j] = 0
			elif i == 0:
				dp[i][j] = dp[i][j - 1] + (0 if B[j - 1] == '1' else oneCountB[j - 1])
			elif j == 0:
				dp[i][j] = dp[i - 1][j] + (0 if A[i - 1] == '1' else oneCountA[i - 1])
			else:
				a = dp[i][j - 1] + (0 if B[j - 1] == '1' else oneCountB[j - 1] + oneCountA[i - 1])
				b = dp[i - 1][j] + (0 if A[i - 1] == '1' else oneCountA[i - 1] + oneCountB[j - 1])
				dp[i][j] = min(a, b)
	print(dp[N][N])


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()
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
gp = []
ans = []

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 hnbhai(tc):
	n = sb()
	a = sa()
	b = sa()
	prefa = [0]
	prefb = [0]
	for i in range(n):
		prefa.append(prefa[-1] + int(a[i]))
		prefb.append(prefb[-1] + int(b[i]))
	dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
	dp[0][0] = 0
	for i in range(n + 1):
		for j in range(n + 1):
			if i == 0 and j == 0:
				continue
			if i == 0:
				dp[i][j] = dp[i][j - 1]
				if b[j - 1] == '0':
					dp[i][j] += prefb[j]
				continue
			if j == 0:
				dp[i][j] = dp[i - 1][j]
				if a[i - 1] == '0':
					dp[i][j] += prefa[i]
				continue
			f = prefa[i] if a[i - 1] == '0' else 0
			s = prefb[j] if b[j - 1] == '0' else 0
			if a[i - 1] == '0':
				dp[i][j] = min(dp[i][j], dp[i - 1][j] + f + prefb[j])
			else:
				dp[i][j] = min(dp[i][j], dp[i - 1][j])
			if b[j - 1] == '0':
				dp[i][j] = min(dp[i][j], dp[i][j - 1] + prefa[i] + s)
			else:
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
	print(dp[n][n])
	return
for _ in range(sb()):
	hnbhai(_ + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	a = '#' + a
	b = input()
	b = '#' + b
	dp = [[10 ** 9] * (n + 1) for i in range(n + 1)]
	pa = [0] * (n + 1)
	pb = [0] * (n + 1)
	for i in range(1, n + 1):
		pa[i] = pa[i - 1] + (a[i] == '1')
	for i in range(1, n + 1):
		pb[i] = pb[i - 1] + (b[i] == '1')
	dp[0][0] = 0
	for i in range(1, n + 1):
		if a[i] == '0':
			dp[i][0] = dp[i - 1][0] + pa[i - 1]
		else:
			dp[i][0] = dp[i - 1][0]
		if b[i] == '0':
			dp[0][i] = dp[0][i - 1] + pb[i - 1]
		else:
			dp[0][i] = dp[0][i - 1]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if a[i] == '0':
				dp[i][j] = dp[i - 1][j] + pa[i - 1] + pb[j]
			else:
				dp[i][j] = dp[i - 1][j]
			if b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i][j - 1] + pb[j - 1] + pa[i])
			else:
				dp[i][j] = min(dp[i][j], dp[i][j - 1])
	print(dp[n][n])


import sys
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):

	def rec(i, j, zeros, memo={}):
		if (i, j) in memo:
			return memo[i, j]
		if i >= n:
			x = s2[j:].count('0')
			count = 0
			for k in range(j, n):
				if s2[k] == '0':
					x -= 1
				else:
					count += x
			return count
		if j >= n:
			x = s1[i:].count('0')
			count = 0
			for k in range(i, n):
				if s1[k] == '0':
					x -= 1
				else:
					count += x
			return count
		elif s1[i] == '1' and s2[j] == '1':
			memo[i, j] = zeros + min(rec(i + 1, j, zeros), rec(i, j + 1, zeros))
			return memo[i, j]
		elif s1[i] == '0' and s2[j] == '0':
			memo[i, j] = min(rec(i + 1, j, zeros - 1), rec(i, j + 1, zeros - 1))
			return memo[i, j]
		elif s1[i] == '0':
			memo[i, j] = min(rec(i + 1, j, zeros - 1), zeros + rec(i, j + 1, zeros))
			return memo[i, j]
		elif s2[j] == '0':
			memo[i, j] = min(rec(i, j + 1, zeros - 1), zeros + rec(i + 1, j, zeros))
			return memo[i, j]
	n = int(input())
	s1 = sys.stdin.readline()
	s2 = sys.stdin.readline()
	z = s1.count('0') + s2.count('0')
	print(rec(0, 0, z))


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 6)
t = int(input())
for _ in range(t):
	n = int(input())
	A = input().strip()
	B = input().strip()

	def get_cnt(s):
		cnt = [0] * n
		zero = 0
		for i in range(n - 1, -1, -1):
			if s[i] == '0':
				zero += 1
			cnt[i] = zero
		return cnt
	cnt_A = get_cnt(A)
	cnt_B = get_cnt(B)
	dp = [[-1] * (n + 1) for i in range(n + 1)]

	def dfs(i, j):
		if i == n and j == n:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		inv = 0
		if i < n:
			inv = cnt_A[i]
		if j < n:
			inv += cnt_B[j]
		ans = float('inf')
		if i < n:
			ans = dfs(i + 1, j) + inv * (A[i] == '1')
		if j < n:
			ans = min(ans, dfs(i, j + 1) + inv * (B[j] == '1'))
		dp[i][j] = ans
		return ans
	print(dfs(0, 0))


import sys
from collections import deque
input = sys.stdin.readline
import math
for t in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	one_1 = [0] * (n + 1)
	one_2 = [0] * (n + 1)
	for i in range(1, n + 1):
		if s1[i - 1] == '1':
			one_1[i] = one_1[i - 1] + 1
		else:
			one_1[i] = one_1[i - 1]
	for i in range(1, n + 1):
		if s2[i - 1] == '1':
			one_2[i] = one_2[i - 1] + 1
		else:
			one_2[i] = one_2[i - 1]
	for j in range(1, n + 1):
		dp[0][j] = dp[0][j - 1] + (one_2[j] if s2[j - 1] == '0' else 0)
	for i in range(1, n + 1):
		dp[i][0] = dp[i - 1][0] + (one_1[i] if s1[i - 1] == '0' else 0)
		for j in range(1, n + 1):
			dp[i][j] = dp[i - 1][j] + (one_1[i] + one_2[j] if s1[i - 1] == '0' else 0)
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + (one_1[i] + one_2[j] if s2[j - 1] == '0' else 0))
	print(dp[-1][-1])


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for i in range(how_much_noob_I_am):
		n = inpu()
		s = inp()
		t = inp()
		dp = [[0] * (n + 1) for i in range(n + 1)]
		dp[0][0] = 0
		prefs = [0]
		for i in range(n):
			if s[i] == '1':
				prefs.append(prefs[-1] + 1)
			else:
				prefs.append(prefs[-1])
		preft = [0]
		for i in range(n):
			if t[i] == '1':
				preft.append(preft[-1] + 1)
			else:
				preft.append(preft[-1])
		for i in range(1, n + 1):
			dp[i][0] = dp[i - 1][0]
			if s[i - 1] == '0':
				dp[i][0] += prefs[i - 1]
		for j in range(1, n + 1):
			dp[0][j] = dp[0][j - 1]
			if t[j - 1] == '0':
				dp[0][j] += preft[j - 1]
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				r = inf
				rr = inf
				if s[i - 1] == '0':
					r = dp[i - 1][j] + prefs[i - 1] + preft[j]
				else:
					r = dp[i - 1][j]
				if t[j - 1] == '0':
					rr = dp[i][j - 1] + prefs[i] + preft[j - 1]
				else:
					rr = dp[i][j - 1]
				dp[i][j] = min(r, rr)
		print(dp[n][n])
main()


import sys
RW = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
from collections import defaultdict as df
import heapq
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in list(input())]
	b = [int(x) for x in list(input())]
	dp = [[0] * (n + 1) for i in range(n + 1)]
	suffixa = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		if a[i] == 0:
			suffixa[i] = suffixa[i + 1] + 1
		else:
			suffixa[i] = suffixa[i + 1]
	suffixb = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		if b[i] == 0:
			suffixb[i] = suffixb[i + 1] + 1
		else:
			suffixb[i] = suffixb[i + 1]
	dp[n][n] = 0
	for i in range(n - 1, -1, -1):
		if a[i] == 0:
			dp[i][n] = dp[i + 1][n]
		else:
			dp[i][n] = dp[i + 1][n] + 1 * suffixa[i + 1]
	for i in range(n - 1, -1, -1):
		if b[i] == 0:
			dp[n][i] = dp[n][i + 1]
		else:
			dp[n][i] = dp[n][i + 1] + 1 * suffixb[i + 1]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			temp1 = dp[j + 1][i] + a[j] * (suffixa[j + 1] + suffixb[i])
			temp2 = dp[j][i + 1] + b[i] * (suffixa[j] + suffixb[i + 1])
			dp[j][i] = min(temp1, temp2)
	print(dp[0][0])


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for i in range(how_much_noob_I_am):
		n = inpu()
		s = inp()
		t = inp()
		prefs = [[0, 0]]
		(one, zero) = (0, 0)
		for i in s:
			if i == '1':
				one += 1
				prefs.append([zero, one])
			else:
				zero += 1
				prefs.append([zero, one])
		preft = [[0, 0]]
		(one, zero) = (0, 0)
		for i in t:
			if i == '1':
				one += 1
				preft.append([zero, one])
			else:
				zero += 1
				preft.append([zero, one])

		@lru_cache(None)
		def fun(x, y):
			if x == n and y == n:
				return 0
			ans = inf
			if x < n:
				p = 0
				if s[x] == '0':
					p = prefs[x][1] + preft[y][1]
				ans = min(ans, p + fun(x + 1, y))
			if y < n:
				p = 0
				if t[y] == '0':
					p = prefs[x][1] + preft[y][1]
				ans = min(ans, p + fun(x, y + 1))
			return ans
		print(fun(0, 0))
main()


from sys import maxsize, setrecursionlimit
setrecursionlimit(10 ** 6)

def solve(i, j, z):
	if (i, j) in dp:
		return dp[i, j]
	if i == -1:
		ans = 0
		while j >= 0:
			if B[j] == '0':
				z += 1
			else:
				ans += z
			j -= 1
		return ans
	if j == -1:
		ans = 0
		while i >= 0:
			if A[i] == '0':
				z += 1
			else:
				ans += z
			i -= 1
		return ans
	ans = maxsize
	if A[i] == '0':
		ans = min(ans, solve(i - 1, j, z + 1))
	else:
		ans = min(ans, z + solve(i - 1, j, z))
	if B[j] == '0':
		ans = min(ans, solve(i, j - 1, z + 1))
	else:
		ans = min(ans, z + solve(i, j - 1, z))
	dp[i, j] = ans
	return ans
for _ in range(int(input())):
	n = int(input())
	A = input()
	B = input()
	dp = {}
	print(solve(n - 1, n - 1, 0))


for _ in range(int(input())):
	num = int(input())
	se = input()
	test = input()
	s = [0 for _ in range(num + 1)]
	t = [0 for _ in range(num + 1)]
	for i in reversed(range(num)):
		s[i] = s[i + 1]
		if se[i] == '0':
			s[i] += 1
		t[i] = t[i + 1]
		if test[i] == '0':
			t[i] += 1
	dynp = [[-1 for _ in range(num + 1)] for _ in range(num + 1)]
	dynp[num][num] = 0
	for i in reversed(range(0, num)):
		dynp[i][num] = dynp[i + 1][num]
		if se[i] == '1':
			dynp[i][num] += s[i]
		dynp[num][i] = dynp[num][i + 1]
		if test[i] == '1':
			dynp[num][i] += t[i]
	for i in reversed(range(num)):
		for j in reversed(range(num)):
			a1 = dynp[i + 1][j]
			if se[i] == '1':
				a1 += s[i] + t[j]
			a2 = dynp[i][j + 1]
			if test[j] == '1':
				a2 += s[i] + t[j]
			dynp[i][j] = min(a1, a2)
	print(dynp[0][0])


def algorithm(l, str1, str2):
	total_cost = [[0 for _ in range(l + 1)] for _ in range(l + 1)]
	how_many_ones_str1 = [0 for _ in range(l + 1)]
	how_many_ones_str2 = [0 for _ in range(l + 1)]
	total_cost[0][0] = 0
	total_cost[0][1] = 0
	total_cost[1][0] = 0
	for i in range(l):
		how_many_ones_str1[i + 1] = how_many_ones_str1[i] + int(str1[i] == '1')
		how_many_ones_str2[i + 1] = how_many_ones_str2[i] + int(str2[i] == '1')
	for i in range(0, l + 1):
		for j in range(0, l + 1):
			if i + j == 0:
				continue
			if i > 0:
				if str1[i - 1] == '1':
					option1 = total_cost[i - 1][j]
				else:
					option1 = total_cost[i - 1][j] + how_many_ones_str1[i - 1]
					if j > 0:
						option1 += how_many_ones_str2[j - 1]
			else:
				option1 = -1
			if j > 0:
				if str2[j - 1] == '1':
					option2 = total_cost[i][j - 1]
				else:
					option2 = total_cost[i][j - 1] + how_many_ones_str2[j - 1]
					if i > 0:
						option2 += how_many_ones_str1[i - 1]
			else:
				option2 = -1
			if (option1 < option2 or option2 == -1) and option1 != -1:
				total_cost[i][j] = option1
			else:
				total_cost[i][j] = option2
	print(total_cost[l][l])

def main():
	number_of_tests = int(input())
	test_cases = [(int(input()), input(), input()) for _ in range(number_of_tests)]
	for (l, a, b) in test_cases:
		algorithm(l, a, b)
try:
	main()
except EOFError:
	pass


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys
import heapq

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
import heapq

def get_set(n):
	ans = 0
	for i in range(21):
		if n & 1 << i > 0:
			ans += 1
	return ans % 2 == 0
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	arr_a = [0] * n
	arr_b = [0] * n
	for i in range(n - 1, -1, -1):
		if a[i] == '0':
			arr_a[i] += 1
		if b[i] == '0':
			arr_b[i] += 1
		if i + 1 < n:
			arr_a[i] += arr_a[i + 1]
			arr_b[i] += arr_b[i + 1]
	dp = [[inf for i in range(n + 1)] for j in range(n + 1)]
	dp[n][n] = 0
	for i in range(n - 1, -1, -1):
		if b[i] == '1':
			dp[n][i] = arr_b[i]
		else:
			dp[n][i] = 0
		dp[n][i] += dp[n][i + 1]
	for i in range(n - 1, -1, -1):
		if a[i] == '1':
			dp[i][n] = arr_a[i]
		else:
			dp[i][n] = 0
		dp[i][n] += dp[i + 1][n]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			cnt1 = arr_a[i]
			cnt2 = arr_b[j]
			if a[i] == '1':
				dp[i][j] = min(dp[i][j], dp[i + 1][j] + cnt1 + cnt2)
			if a[i] == '0':
				dp[i][j] = min(dp[i][j], dp[i + 1][j])
			if b[j] == '1':
				dp[i][j] = min(dp[i][j], dp[i][j + 1] + cnt1 + cnt2)
			if b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i][j + 1])
	print(dp[0][0])


tt = int(input())
while tt > 0:
	n = int(input())
	a = str(input())
	b = str(input())
	pref = []
	pref1 = []
	for i in range(n + 1):
		pref.append(0)
		pref1.append(0)
	dp = []
	for i in range(n + 1):
		t = []
		for j in range(n + 1):
			t.append(1e+18)
		dp.append(t)
	dp[n][n] = 0
	for i in range(n - 1, -1, -1):
		pref[i] = pref[i + 1]
		pref[i] += a[i] == '0'
		pref1[i] = pref1[i + 1]
		pref1[i] += b[i] == '0'
	for i in range(n - 1, -1, -1):
		dp[n][i] = dp[n][i + 1]
		if b[i] == '1':
			dp[n][i] += pref[n] + pref1[i]
	for i in range(n - 1, -1, -1):
		dp[i][n] = dp[i + 1][n]
		if a[i] == '1':
			dp[i][n] += pref[i] + pref1[n]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if a[i] == '0' and b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i + 1][j])
				dp[i][j] = min(dp[i][j], dp[i][j + 1])
			elif a[i] == '0' and b[j] == '1':
				dp[i][j] = min(dp[i][j], dp[i + 1][j])
				dp[i][j] = min(dp[i][j], dp[i][j + 1] + pref[i] + pref1[j])
			elif a[i] == '1' and b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i][j + 1])
				dp[i][j] = min(dp[i][j], dp[i + 1][j] + pref[i] + pref1[j])
			else:
				dp[i][j] = min(dp[i][j], dp[i + 1][j] + pref[i] + pref1[j])
				dp[i][j] = min(dp[i][j], dp[i][j + 1] + pref[i] + pref1[j])
	print(dp[0][0])
	tt = tt - 1


import bisect
import math
import string
from collections import deque, Counter
import sys
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7
dp = [[-1] * 501 for i in range(501)]

def solve():
	n = int(input())
	s1 = input()
	s2 = input()
	p1 = [0] * (n + 1)
	p2 = [0] * (n + 1)
	m = [[1000000000000000000] * (n + 1) for i in range(n + 1)]
	m[n][n] = 0
	for i in range(n - 1, -1, -1):
		p1[i] = p1[i + 1] + (s1[i] == '0')
		p2[i] = p2[i + 1] + (s2[i] == '0')
	for i in range(n - 1, -1, -1):
		m[n][i] = m[n][i + 1]
		if s2[i] == '1':
			m[n][i] += p1[n] + p2[i]
	for i in range(n - 1, -1, -1):
		m[i][n] = m[i + 1][n]
		if s1[i] == '1':
			m[i][n] += p1[i] + p2[n]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if s1[i] == '0' and s2[j] == '0':
				m[i][j] = min(m[i][j], m[i + 1][j])
				m[i][j] = min(m[i][j], m[i][j + 1])
			elif s1[i] == '0' and s2[j] == '1':
				m[i][j] = min(m[i][j], m[i + 1][j])
				m[i][j] = min(m[i][j], m[i][j + 1] + p1[i] + p2[j])
			elif s1[i] == '1' and s2[j] == '0':
				m[i][j] = min(m[i][j], m[i][j + 1])
				m[i][j] = min(m[i][j], m[i + 1][j] + p1[i] + p2[j])
			else:
				m[i][j] = min(m[i][j], m[i + 1][j] + p1[i] + p2[j])
				m[i][j] = min(m[i][j], m[i][j + 1] + p1[i] + p2[j])
	print(m[0][0])
for testis in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	pref = [0] * (n + 1)
	pref1 = [0] * (n + 1)
	dp = [[float('inf') for i in range(n + 1)] for j in range(n + 1)]
	dp[n][n] = 0
	for i in range(n - 1, -1, -1):
		pref[i] = pref[i + 1] + int(a[i] == '0')
		pref1[i] = pref1[i + 1] + int(b[i] == '0')
	for i in range(n - 1, -1, -1):
		dp[n][i] = dp[n][i + 1]
		if b[i] == '1':
			dp[n][i] += pref[n] + pref1[i]
	for i in range(n - 1, -1, -1):
		dp[i][n] = dp[i + 1][n]
		if a[i] == '1':
			dp[i][n] += pref[i] + pref1[n]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, -1, -1):
			if a[i] == '0' and b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i + 1][j])
				dp[i][j] = min(dp[i][j], dp[i][j + 1])
			elif a[i] == '0' and b[j] == '1':
				dp[i][j] = min(dp[i][j], dp[i + 1][j])
				dp[i][j] = min(dp[i][j], dp[i][j + 1] + pref[i] + pref1[j])
			elif a[i] == '1' and b[j] == '0':
				dp[i][j] = min(dp[i][j], dp[i][j + 1])
				dp[i][j] = min(dp[i][j], dp[i + 1][j] + pref[i] + pref1[j])
			else:
				dp[i][j] = min(dp[i][j], dp[i + 1][j] + pref[i] + pref1[j])
				dp[i][j] = min(dp[i][j], dp[i][j + 1] + pref[i] + pref1[j])
	print(dp[0][0])


from functools import lru_cache
import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		t = input()
		pres = [[0, 0]]
		(a, b) = (0, 0)
		for i in range(n):
			if s[i] == '1':
				b += 1
				pres.append([a, b])
			else:
				a += 1
				pres.append([a, b])
		pret = [[0, 0]]
		(a, b) = (0, 0)
		for i in range(n):
			if t[i] == '1':
				b += 1
				pret.append([a, b])
			else:
				a += 1
				pret.append([a, b])

		@lru_cache(None)
		def fun(x, y):
			if x == n and y == n:
				return 0
			ans = float('inf')
			if x < n:
				p = 0
				if s[x] == '0':
					p = pres[x][1] + pret[y][1]
				ans = min(ans, p + fun(x + 1, y))
			if y < n:
				p = 0
				if t[y] == '0':
					p = pres[x][1] + pret[y][1]
				ans = min(ans, p + fun(x, y + 1))
			return ans
		print(fun(0, 0))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
sys.setrecursionlimit(10 ** 6)
d = {}

def solve(i, j, a, b, ar, br):
	n = len(a)
	try:
		return d[i, j]
	except:
		pass
	if i >= n and j >= n:
		return 0
	if i >= n:
		if b[j] == '1':
			d[i, j] = br[j]
		else:
			d[i, j] = 0
		d[i, j] += solve(i, j + 1, a, b, ar, br)
		return d[i, j]
	if j >= n:
		if a[i] == '1':
			d[i, j] = ar[i]
		else:
			d[i, j] = 0
		d[i, j] += solve(i + 1, j, a, b, ar, br)
		return d[i, j]
	if a[i] == '1':
		ans1 = ar[i] + br[j] + solve(i + 1, j, a, b, ar, br)
	else:
		ans1 = solve(i + 1, j, a, b, ar, br)
	if b[j] == '1':
		ans2 = ar[i] + br[j] + solve(i, j + 1, a, b, ar, br)
	else:
		ans2 = solve(i, j + 1, a, b, ar, br)
	d[i, j] = min(ans1, ans2)
	return d[i, j]
for jfjf in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(input())
	ar = []
	br = []
	sum = 0
	d = {}
	for i in range(-1, -n - 1, -1):
		if a[i] == '0':
			sum += 1
		ar.append(sum)
	sum = 0
	for i in range(-1, -n - 1, -1):
		if b[i] == '0':
			sum += 1
		br.append(sum)
	ar.reverse()
	br.reverse()
	print(solve(0, 0, a, b, ar, br))


def checkmin(a, b):
	dp = [[0 for i in range(len(a) + 1)] for j in range(len(a) + 1)]
	suf = [0]
	n = len(a)
	for i in range(n - 1, -1, -1):
		suf.append(suf[-1] + (a[i] == '0'))
	suf = suf[::-1]
	pre = [0]
	for i in range(n):
		pre.append(pre[-1] + (a[i] == '1'))
	for i in range(1, n + 1):
		for j in range(n + 1):
			if b[i - 1] == '0':
				if j == 0:
					dp[i][j] = dp[i - 1][j] + pre[j]
				else:
					dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + pre[j])
			elif j == 0:
				dp[i][j] = dp[i - 1][j] + suf[j]
			else:
				dp[i][j] = min(dp[i][j - 1], dp[i - 1][j] + suf[j])
	res = 0
	tot = a.count('0')
	for i in a:
		if i == '1':
			res += tot
		else:
			tot -= 1
	tot = b.count('0')
	for i in b:
		if i == '1':
			res += tot
		else:
			tot -= 1
	return res + dp[-1][-1]
t = int(input())
for _ in range(t):
	t -= 1
	n = int(input())
	a = input()
	b = input()
	print(checkmin(a, b))


def count_ones(arr1, arr2, i, j):
	return arr1[i] + arr2[j]
t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	prefix_ones_s1 = [0]
	prefix_ones_s2 = [0]
	for i in range(n):
		if s1[i] == '1':
			prefix_ones_s1.append(prefix_ones_s1[-1] + 1)
		else:
			prefix_ones_s1.append(prefix_ones_s1[-1])
		if s2[i] == '1':
			prefix_ones_s2.append(prefix_ones_s2[-1] + 1)
		else:
			prefix_ones_s2.append(prefix_ones_s2[-1])
	dp = []
	for i in range(n + 1):
		dp.append([float('inf') for j in range(n + 1)])
	dp[0][0] = 0
	for i in range(1, n + 1):
		if s2[i - 1] == '0':
			dp[0][i] = dp[0][i - 1] + count_ones(prefix_ones_s1, prefix_ones_s2, 0, i - 1)
		else:
			dp[0][i] = dp[0][i - 1]
	for i in range(1, n + 1):
		if s1[i - 1] == '0':
			dp[i][0] = dp[i - 1][0] + count_ones(prefix_ones_s1, prefix_ones_s2, i - 1, 0)
		else:
			dp[i][0] = dp[i - 1][0]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if s2[j - 1] == '0':
				choice1 = dp[i][j - 1] + count_ones(prefix_ones_s1, prefix_ones_s2, i, j - 1)
			else:
				choice1 = dp[i][j - 1]
			if s1[i - 1] == '0':
				choice2 = dp[i - 1][j] + count_ones(prefix_ones_s1, prefix_ones_s2, i - 1, j)
			else:
				choice2 = dp[i - 1][j]
			dp[i][j] = min(choice1, choice2)
	print(dp[-1][-1])


def solve(n):
	s1 = input()
	s2 = input()
	dp = [[[float('inf'), 0] for i in range(n + 1)] for i in range(n + 1)]
	dp[0][0][0] = 0
	for i in range(n):
		dp[i + 1][0][0] = dp[i][0][0]
		dp[i + 1][0][1] = dp[i][0][1]
		if s1[i] == '1':
			dp[i + 1][0][1] += 1
		else:
			dp[i + 1][0][0] += dp[i][0][1]
	for i in range(n):
		dp[0][i + 1][0] = dp[0][i][0]
		dp[0][i + 1][1] = dp[0][i][1]
		if s2[i] == '1':
			dp[0][i + 1][1] += 1
		else:
			dp[0][i + 1][0] += dp[0][i][1]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if s1[i - 1] == '1':
				dp[i][j][1] = dp[i - 1][j][1] + 1
				dp[i][j][0] = dp[i - 1][j][0]
			else:
				dp[i][j][1] = dp[i - 1][j][1]
				dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]
			if s2[j - 1] == '1':
				x = dp[i][j - 1][0]
				if x < dp[i][j][0]:
					dp[i][j][0] = x
					dp[i][j][1] = dp[i][j - 1][1] + 1
			else:
				x = dp[i][j - 1][0] + dp[i][j - 1][1]
				if x < dp[i][j][0]:
					dp[i][j][0] = x
					dp[i][j][1] = dp[i][j - 1][1]
	print(dp[-1][-1][0])
for _ in range(int(input())):
	n = int(input())
	solve(n)


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	from functools import lru_cache
	for _ in range(int(input())):
		n = int(input())
		s = input()
		t = input()
		prefix = [[0, 0]]
		for i in range(n):
			if s[i] == '1':
				prefix.append([prefix[-1][0], prefix[-1][1] + 1])
			else:
				prefix.append([prefix[-1][0] + 1, prefix[-1][1]])
		p1 = [[0, 0]]
		for i in range(n):
			if t[i] == '1':
				p1.append([p1[-1][0], p1[-1][1] + 1])
			else:
				p1.append([p1[-1][0] + 1, p1[-1][1]])

		@lru_cache(None)
		def dfs(i, j):
			if i == n and j == n:
				return 0
			ans = float('inf')
			if i < n:
				l = prefix[i][1] + p1[j][1] if s[i] == '0' else 0
				ans = min(ans, l + dfs(i + 1, j))
			if j < n:
				l = prefix[i][1] + p1[j][1] if t[j] == '0' else 0
				ans = min(ans, l + dfs(i, j + 1))
			return ans
		print(dfs(0, 0))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
sys.setrecursionlimit(10 ** 6)
inf = 1000000000

def go(i, j, ones, n, a, b, dp):
	if i == n and j == n:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	(c1, c2) = (inf, inf)
	if i != n:
		if a[i] == '1':
			c1 = go(i + 1, j, ones + 1, n, a, b, dp)
		else:
			c1 = ones + go(i + 1, j, ones, n, a, b, dp)
	if j != n:
		if b[j] == '1':
			c2 = go(i, j + 1, ones + 1, n, a, b, dp)
		else:
			c2 = ones + go(i, j + 1, ones, n, a, b, dp)
	dp[i][j] = min(c1, c2)
	return dp[i][j]
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
	print(go(0, 0, 0, n, a, b, dp))


import sys
sys.setrecursionlimit(1000000)

def helper(i, j, count, n):
	if i == n and j == n:
		return 0
	elif (i, j) in dp:
		return dp[i, j]
	elif i == n:
		if b[j] == '1':
			dp[i, j] = helper(i, j + 1, count + 1, n)
		else:
			dp[i, j] = count + helper(i, j + 1, count, n)
	elif j == n:
		if a[i] == '1':
			dp[i, j] = helper(i + 1, j, count + 1, n)
		else:
			dp[i, j] = count + helper(i + 1, j, count, n)
	elif a[i] != b[j]:
		if a[i] == '0':
			dp[i, j] = count + helper(i + 1, j, count, n)
		else:
			dp[i, j] = count + helper(i, j + 1, count, n)
	elif a[i] == '0':
		dp[i, j] = count + min(helper(i + 1, j, count, n), helper(i, j + 1, count, n))
	else:
		dp[i, j] = min(helper(i + 1, j, count + 1, n), helper(i, j + 1, count + 1, n))
	return dp[i, j]
t = int(sys.stdin.readline())
for tt in range(t):
	n = int(sys.stdin.readline())
	a = sys.stdin.readline()
	b = sys.stdin.readline()
	dp = {}
	sys.stdout.write(str(helper(0, 0, 0, n)) + '\n')


def pprint(d):
	for row in d:
		print(*row[1:])
T = int(input())
for T in range(T):
	n = int(input())
	a = input()
	b = input()
	aa = [0]
	bb = [0]
	acount = 0
	bcount = 0
	for i in range(n):
		if a[i] == '1':
			acount += 1
		if b[i] == '1':
			bcount += 1
		aa.append(acount)
		bb.append(bcount)
	d = [[n * n for i in range(n + 1)] for i in range(n + 1)]
	d[1][0] = 0
	for row in range(1, n + 1):
		for col in range(1, n + 1):
			vara = d[row][col - 1]
			if a[col - 1] == '0':
				vara += bb[row - 1] + aa[col]
			varb = d[row - 1][col]
			if b[row - 1] == '0':
				varb += bb[row] + aa[col - 1]
			d[row][col] = min(vara, varb)
	print(d[n][n])


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	t = input()
	zs = [0 for _ in range(n + 1)]
	zt = [0 for _ in range(n + 1)]
	for i in reversed(range(n)):
		zs[i] = zs[i + 1]
		if s[i] == '0':
			zs[i] += 1
		zt[i] = zt[i + 1]
		if t[i] == '0':
			zt[i] += 1
	dp = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
	dp[n][n] = 0
	for i in reversed(range(0, n)):
		dp[i][n] = dp[i + 1][n]
		if s[i] == '1':
			dp[i][n] += zs[i]
		dp[n][i] = dp[n][i + 1]
		if t[i] == '1':
			dp[n][i] += zt[i]
	for i in reversed(range(n)):
		for j in reversed(range(n)):
			x1 = dp[i + 1][j]
			if s[i] == '1':
				x1 += zs[i] + zt[j]
			x2 = dp[i][j + 1]
			if t[j] == '1':
				x2 += zs[i] + zt[j]
			dp[i][j] = min(x1, x2)
	print(dp[0][0])