You are given two strings $S$ and $R$. Each of these strings has length $N$. We want to make $S$ equal to $R$ by performing the following operation some number of times (possibly zero):
- Choose two integers $a$ and $b$ such that $1 \le a \le b \le N$.
- For each $i$ such that $a \le i \le b$, replace the $i$-th character of $S$ by the $i$-th character of $R$.
Suppose that we make $S$ equal to $R$ by performing this operation $k$ times, in such a way that the total number of replaced characters (i.e. the sum of all $k$ values of $b-a+1$) is $l$. Then, the cost of this process is defined as $k \cdot l$.
Find the minimum cost with which we can make $S$ equal to $R$.

-----Input-----
- The first line of the 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 string $S$.
- The second line contains a single string $R$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum cost.

-----Constraints-----
- $1 \le T \le 4,000$
- $1 \le N \le 10^6$
- $|S| = |R| = N$
- $S$ and $R$ contain only lowercase English letters
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
1
adefb
bdefa

-----Example Output-----
4

-----Explanation-----
Example case 1: $S$ can be made equal to $R$ in two moves. First, we replace $S_1$ by $R_1$ and then replace $S_5$ by $R_5$. We have $k = l = 2$, so the cost is $2 \cdot 2 = 4$. If we wanted to perform only one operation, the cost would be $5$.

Difficulty: HARD
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	s = input()
	r = input()
	a = []
	l = 0
	k = 0
	tmp = 0
	cnt = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			if cnt == 0:
				k += 1
			cnt += 1
			l += 1
			if tmp:
				a.append(tmp)
				tmp = 0
		else:
			if k:
				tmp += 1
			cnt = 0
	ans = k * l
	a.sort()
	if k == 1:
		print(k * l)
		continue
	for i in a:
		k -= 1
		l += i
		ans = min(ans, k * l)
	print(ans)


t = int(input())
while t != 0:
	s = input()
	r = input()
	n = len(s)
	k = 0
	c = 0
	crlen = 0
	ans = 0
	j = 0
	a = []
	for i in range(0, n, 1):
		if s[i] != r[i]:
			if crlen > 0 and j == 1:
				a.append(crlen)
				k = k + 1
			elif j == 0:
				k = k + 1
			crlen = 0
			j = 1
			c = c + 1
		else:
			crlen = crlen + 1
	a.sort()
	ans = c * k
	for i in a:
		c = c + i
		k = k - 1
		ans = min(ans, c * k)
	print(ans)
	t = t - 1


from itertools import accumulate as ac
for _ in range(int(input())):
	s = ''.join(('* '[x != y] for (x, y) in zip(input(), input()))).strip('*')
	print(min((k * (len(s) - x) for (k, x) in enumerate(ac([0] + sorted(map(len, s.split()), reverse=True)), 1))))


for _ in range(int(input())):
	s = input()
	r = input()
	a = []
	b = []
	k = 0
	lenth = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			lenth += 1
			k += 1
			a.append(i)
	for j in range(1, len(a)):
		b.append(a[j] - a[j - 1] - 1)
	b.sort()
	ans = k * lenth
	for i in range(len(b)):
		lenth += b[i]
		k = k - 1
		ans = min(k * lenth, ans)
	print(ans)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	s = input()
	r = input()
	a = [1]
	b = []
	if s[0] == r[0]:
		b.append(0)
	else:
		b.append(1)
	for i in range(1, len(s)):
		if s[i] == r[i]:
			bit = 0
		else:
			bit = 1
		if bit == b[-1]:
			a[-1] += 1
		else:
			b.append(bit)
			a.append(1)
	if b[0] == 0:
		b = b[1:]
		a = a[1:]
	if len(b) == 0:
		print('0')
		continue
	if b[-1] == 0:
		b = b[:len(b) - 1]
		a = a[:len(a) - 1]
	if len(b) == 1:
		print(a[0])
		continue
	(p, l) = ([], 0)
	for i in range(len(b)):
		if b[i] == 1:
			l += a[i]
		else:
			p.append(a[i])
	p.sort()
	k = b.count(1)
	ans = [k * l]
	for i in range(len(p)):
		l += p[i]
		k -= 1
		ans.append(l * k)
	print(min(ans))


import sys
input = sys.stdin.readlines
print = sys.stdout.write
t = input()
for case in range(1, int(t[0]) * 2, 2):
	s = t[case]
	r = t[case + 1]
	unlike = []
	curr = None
	l = 0
	k = 0
	for i in range(len(s) - 1):
		if r[i] != s[i]:
			l += 1
			if curr:
				unlike.append(curr)
				k += 1
			curr = 0
		elif curr != None:
			curr += 1
	k += 1
	unlike.sort()
	mini = k * l
	for (i, j) in enumerate(unlike):
		k -= 1
		l += j
		mini = min(mini, k * l)
	print(str(mini) + '\n')


for i in range(int(input())):
	s = input()
	r = input()
	(k, l, f) = (0, 0, 0)
	ff = []
	farhan = False
	for i in range(len(s)):
		if s[i] == r[i]:
			if farhan:
				f += 1
		else:
			if not farhan:
				k += 1
			farhan = True
			l += 1
			if f > 0:
				k += 1
				ff.append(f)
				f = 0
	ff.sort()
	sol = k * l
	for i in range(len(ff)):
		l += ff[i]
		k -= 1
		sol = min(sol, k * l)
	print(sol)


for _ in range(int(input())):
	S = input()
	R = input()
	N = len(S)
	groups = []
	cont = False
	for i in range(N):
		if S[i] != R[i]:
			if cont:
				groups[-1][1] += 1
			else:
				groups.append([i, i])
				cont = True
		else:
			cont = False
	k = len(groups)
	l = 0
	diff = []
	for i in range(1, k):
		diff.append(groups[i][0] - groups[i - 1][1] - 1)
		l += groups[i][1] - groups[i][0] + 1
	if len(groups) > 0:
		l += groups[0][1] - groups[0][0] + 1
	diff.sort()
	mx = k * l
	for i in range(len(groups) - 1):
		k -= 1
		l += diff[i]
		mx = min(mx, k * l)
	print(mx)


for _ in range(int(input())):
	s = input()
	r = input()
	unlike = []
	curr = None
	l = 0
	k = 0
	for i in range(len(s)):
		if r[i] != s[i]:
			l += 1
			if curr:
				unlike.append(curr)
				k += 1
			curr = 0
		elif curr != None:
			curr += 1
	k += 1
	unlike.sort()
	mini = k * l
	for (i, j) in enumerate(unlike):
		k -= 1
		l += j
		mini = min(mini, k * l)
	print(mini)


for _ in range(int(input())):
	S = str(input())
	R = str(input())
	N = len(S)
	Gaplist = []
	(GapLength, Length, NoOfSwap) = (0, 0, 0)
	flag = False
	for i in range(N):
		if S[i] == R[i]:
			if flag:
				GapLength += 1
		else:
			if not flag:
				NoOfSwap += 1
			flag = True
			Length += 1
			if GapLength > 0:
				NoOfSwap += 1
				Gaplist.append(GapLength)
				GapLength = 0
	Gaplist.sort()
	MinPossibleOutcome = NoOfSwap * Length
	for i in range(len(Gaplist)):
		NoOfSwap -= 1
		Length += Gaplist[i]
		MinPossibleOutcome = min(MinPossibleOutcome, NoOfSwap * Length)
	print(MinPossibleOutcome)


for _ in range(int(input())):
	s = str(input())
	r = str(input())
	flag = 0
	cp = 0
	k = 0
	t = 0
	l = []
	for i in range(len(s)):
		if r[i] == s[i]:
			if flag == 1:
				cp += 1
		else:
			if flag == 0:
				k += 1
			flag = 1
			t += 1
			if cp > 0:
				k += 1
				l.append(cp)
				cp = 0
	ans = t * k
	l.sort()
	for i in l:
		k -= 1
		t += i
		ans = min(ans, k * t)
	print(ans)


for t in range(int(input())):
	e_islands = []
	u_islands = []
	s = input()
	r = input()
	gap = 0
	size = 0
	mismatches = 0
	for i in range(len(s)):
		if s[i] == r[i]:
			gap += 1
			if size != 0:
				u_islands.append(size)
				size = 0
		else:
			size += 1
			if gap != 0:
				e_islands.append(gap)
				gap = 0
			mismatches += 1
	if size != 0:
		u_islands.append(size)
	if s[0] == r[0]:
		e_islands = e_islands[1:]
	e_islands = sorted(e_islands)
	min_len = mismatches
	k = len(u_islands)
	ans = min_len * k
	for val in e_islands:
		min_len += val
		k -= 1
		ans = min(ans, min_len * k)
	print(ans)


for _ in range(int(input())):
	s = input()
	ss = input()
	ind = [i for i in range(len(s)) if s[i] != ss[i]]
	a = [ind[i + 1] - ind[i] - 1 for i in range(len(ind) - 1)]
	a.sort()
	(ig, ire) = (len(ind), len(ind))
	b = [ig * ire]
	for i in a:
		ig -= 1
		ire += i
		b.append(ig * ire)
	print(min(b))


t = int(input())
for _ in range(t):
	string_s = input()
	string_r = input()
	n = len(string_r)
	Queue = []
	gaps = 0
	candoGaps = 0
	k = 0
	l = 0
	for i in range(n):
		if string_r[i] == string_s[i]:
			if candoGaps == 1:
				gaps += 1
		else:
			l += 1
			if candoGaps == 0:
				candoGaps = 1
				k += 1
			if gaps > 0:
				Queue.append(gaps)
				gaps = 0
				k += 1
	Queue.sort()
	res = k * l
	while k > 0 and Queue:
		k -= 1
		l += Queue.pop(0)
		if res > k * l:
			res = l * k
	print(res)
exit(0)


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
mp = lambda : map(int, input().split())
for _ in range(int(input())):
	s = input()
	r = input()
	n = len(s)
	dp = [0 for i in range(n)]
	for i in range(n):
		if s[i] != r[i]:
			dp[i] = 1
	prev = -1
	l = dp.count(1)
	k = 0
	z = []
	for i in range(n):
		if prev != 1 and dp[i] == 1:
			k += 1
			z.append([i, i])
		elif dp[i] == 1:
			z[-1][1] += 1
		prev = dp[i]
	diff = []
	for i in range(len(z) - 1):
		(i1, i2) = (z[i], z[i + 1])
		diff.append(i2[0] - i1[1] - 1)
	ans = k * l
	diff.sort()
	for i in diff:
		l += i
		k -= 1
		ans = min(ans, k * l)
	print(ans)


import heapq

def minops(s, r):
	letter = 0
	heap = []
	k = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			letter += 1
			if i + 1 == len(s) or s[i + 1] == r[i + 1]:
				k += 1
				g = 0
		elif k != 0:
			g += 1
			if i + 1 != len(s) and s[i + 1] != r[i + 1]:
				heapq.heappush(heap, g)
	mini = k * letter
	while k > 0 and len(heap) > 0:
		k -= 1
		gap = heapq.heappop(heap)
		letter += gap
		if k * letter < mini:
			mini = k * letter
	return mini
t = int(input())
for _ in range(t):
	s = input()
	r = input()
	print(minops(s, r))


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	pos = []
	gaps = []
	roast = [1]
	l = 0
	k = 0
	least = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			pos.append(i)
			if len(pos) > 1:
				j = len(pos) - 1
				if pos[j - 1] + 1 != pos[j]:
					gaps.append(pos[j] - pos[j - 1] - 1)
					roast.append(1)
				else:
					roast[-1] += 1
	l = len(pos)
	k = len(roast)
	least = l * k
	gaps.sort()
	for ele in gaps:
		l += ele
		k -= 1
		if l * k < least:
			least = l * k
	print(least)


from collections import *
from bisect import *
from math import *
import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	s = input().rstrip()
	r = input().rstrip()
	rr = len(s)
	ind = []
	for i in range(len(s)):
		if s[i] != r[i]:
			ind.append(i + 1)
	ind1 = []
	for i in range(len(ind) - 1):
		ind1.append(ind[i + 1] - ind[i])
	rr = len(ind) * len(ind)
	k = len(ind)
	l = len(ind)
	ind1.sort()
	for i in ind1:
		l += i - 1
		k -= 1
		rr = min(rr, k * l)
	print(rr)


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	l = []
	i = l1 = k = 0
	while i < n:
		if a[i] != b[i]:
			while i < n and a[i] != b[i]:
				i += 1
				l1 += 1
			k += 1
		else:
			c = 0
			while i < n and a[i] == b[i]:
				c += 1
				i += 1
			l.append(c)
	if k == 0:
		print(0)
	else:
		if a[0] == b[0]:
			l.pop(0)
		if a[n - 1] == b[n - 1]:
			l.pop(-1)
		l.sort()
		m = k * l1
		i = 0
		for j in range(k - 1, 0, -1):
			l1 = l1 + l[i]
			i += 1
			m = min(l1 * j, m)
		print(m)


for t in range(int(input())):
	s = input()
	r = input()
	diff = list()
	index = list()
	cnt = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			cnt += 1
			index.append(i)
	for i in range(1, len(index)):
		diff.append(index[i] - index[i - 1] - 1)
	diff.sort()
	fmin = cnt ** 2
	oper = cnt
	moves = cnt
	for i in diff:
		moves += i
		oper -= 1
		fmin = min(fmin, moves * oper)
	print(fmin)


tests = int(input())
for _ in range(tests):
	strA = input()
	strB = input()
	minL = 0
	sections = 0
	equalGap = 0
	equalGaps = []
	previousDiff = False
	for i in range(len(strA)):
		letterA = strA[i]
		letterB = strB[i]
		if letterA != letterB:
			minL += 1
			if equalGap != 0:
				equalGaps.append(equalGap)
			if not previousDiff:
				sections += 1
			equalGap = 0
			previousDiff = True
		else:
			equalGap += 1
			previousDiff = False
	equalGaps.sort(reverse=True)
	result = sections * minL
	while sections > 1:
		removeOneMin = equalGaps.pop()
		minL += removeOneMin
		sections -= 1
		result = min(result, sections * minL)
	print(result)


from itertools import accumulate
I = input
t = int(I())
for _ in range(t):
	s = ''.join(('* '[x != y] for (x, y) in zip(I(), I()))).strip('*')
	r = min((k * (len(s) - x) for (k, x) in enumerate(accumulate([0] + sorted(map(len, s.split()), reverse=True)), 1)))
	print(r)


T = int(input())
for j in range(T):
	s = input()
	r = input()
	t = []
	c = None
	(n, k) = (0, 0)
	for i in range(len(s)):
		if r[i] != s[i]:
			n += 1
			if c:
				t.append(c)
				k += 1
			c = 0
		elif c != None:
			c += 1
	k += 1
	t.sort()
	m = k * n
	for (i, j) in enumerate(t):
		k -= 1
		n += j
		m = min(m, k * n)
	print(m)


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	ans = 1000000000000000
	c = 0
	l = 0
	k = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			c += 1
			l += 1
			if c == 1:
				k += 1
		else:
			c = 0
	a = 0
	b = 0
	ans = k * l
	for i in range(len(s) - 1, -1, -1):
		if s[i] != r[i]:
			b = i
			break
	for i in range(len(s)):
		if s[i] != r[i]:
			a = i
			break
	gap = []
	c = 0
	for i in range(a, b + 1):
		if s[i] == r[i]:
			c += 1
		elif c != 0:
			gap.append(c)
			c = 0
	gap.sort()
	for i in gap:
		k -= 1
		l += i
		ans = min(ans, k * l)
	print(ans)


import sys
for _ in range(int(input())):
	s = input()
	r = input()
	l = 0
	length = len(s)
	for i in range(length):
		if s[i] != r[i]:
			l += 1
	islands = []
	ind1 = -1
	ind2 = -1
	for i in range(length):
		if s[i] != r[i]:
			if ind1 == -1:
				ind1 = i
				ind2 = i
			else:
				ind2 = i
		elif ind1 != -1 and ind2 != -1:
			islands.append([ind1, ind2])
			ind1 = -1
			ind2 = -1
	if ind1 != -1 and ind2 != -1:
		islands.append([ind1, ind2])
	gap_arr = []
	for i in range(len(islands) - 1):
		gap_arr.append(islands[i + 1][0] - islands[i][1] - 1)
	gap_arr.sort()
	k = len(islands)
	ans = l * k
	for i in range(0, len(islands) - 1):
		k = k - 1
		l = l + gap_arr[i]
		ans = min(ans, l * k)
	print(ans)


for _ in range(int(input())):
	s = input()
	r = input()
	L = []
	a = 0
	b = 0
	for i in range(len(s)):
		if s[i] == r[i]:
			a += 1
		else:
			L.append(a)
			b += 1
			a = 0
	L = L[1:]
	L.sort()
	sol = b * b
	a = b
	for ele in L:
		b = b - 1
		a = a + ele
		x = a * b
		sol = min(x, sol)
	print(sol)


for j in range(int(input())):
	s = input()
	r = input()
	x = []
	for i in range(len(s)):
		if s[i] != r[i]:
			x.append(i)
	aman = []
	k = 1
	l = len(x)
	for i in range(len(x) - 1):
		if x[i + 1] == x[i] + 1:
			k += 0
		else:
			k += 1
		if x[i + 1] - x[i] - 1 != 0:
			aman.append(x[i + 1] - x[i] - 1)
	aman.sort()
	ans = k * l
	for i in range(len(aman)):
		l += aman[i]
		k = k - 1
		ans = min(ans, k * l)
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	a = []
	n = len(s)
	diff = 0
	for i in range(n):
		if s[i] != r[i]:
			a.append(i)
			diff += 1
	d = []
	for i in range(1, diff):
		d.append(a[i] - a[i - 1] - 1)
	d.sort()
	cost = diff * diff
	k = diff
	l = diff
	i = 0
	for k in range(diff - 1, 0, -1):
		if i >= len(d):
			break
		l += d[i]
		cost = min(cost, k * l)
		i += 1
	print(cost)


for _ in range(int(input())):
	s = input()
	r = input()
	if s == r:
		print('0')
		continue
	l = [a == b for (a, b) in zip(s, r)]
	temp = l[0]
	count = 0
	dream = []
	for i in l:
		if temp == i:
			count += 1
		else:
			dream.append(count)
			temp = i
			count = 1
	dream.append(count)
	if l[0]:
		dream.pop(0)
	if l[-1]:
		dream.pop(-1)
	l.clear()
	p = sum(dream)
	lenth_dream = len(dream)
	if lenth_dream == 1:
		print(dream[0])
		dream.clear()
		continue
	delt = [p for i in range(1, lenth_dream // 2 + 1)]
	listOfOnes = dream[1::2]
	listOfOnes.sort(reverse=True)
	dream.clear()
	summ = 0
	for i in range(len(delt)):
		summ += listOfOnes[i]
		delt[i] -= summ
		delt[i] = (i + 2) * delt[i]
	if min(delt) > p:
		print(p)
		delt.clear()
		listOfOnes.clear()
		continue
	print(min(delt))
	delt.clear()
	listOfOnes.clear()


t = int(input())
for _ in range(t):
	s1 = input()
	s2 = input()
	n = len(s1)
	max_k = 0
	min_l = 0
	flag = 0
	lst = []
	i = 0
	while i < n:
		j = i
		while j < n and s1[j] == s2[j]:
			j += 1
		if j == n:
			break
		if flag != 0:
			lst.append(j - i)
		i = j
		while j < n and s1[j] != s2[j]:
			flag = 1
			j += 1
		min_l += j - i
		max_k += 1
		i = j
	lst.sort()
	Min = min_l * max_k
	index = 0
	while max_k >= 1 and index < len(lst):
		max_k -= 1
		min_l += lst[index]
		Min = min(Min, max_k * min_l)
		index += 1
	print(Min)


from itertools import accumulate, count
from operator import sub, mul
try:
	t = int(input())
	for i in range(t):
		s = input()
		r = input()
		z = zip(s, r)
		s = ''.join(('* '[x != y] for (x, y) in z)).strip('*')
		a = accumulate([len(s)] + sorted(map(len, s.split()), reverse=True), sub)
		steps = min(map(mul, count(1), a))
		print(steps)
except:
	pass


try:
	from collections import Counter
	from sys import stdin, stdout

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

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

	def get_string():
		return stdin.readline().strip()

	def get_singleInt():
		return int(stdin.readline())

	def main():
		testCases = get_singleInt()
		for i in range(testCases):
			stringA = get_string()
			stringB = get_string()
			minOperationsRequired(stringA, stringB)

	def minOperationsRequired(stringA, stringB):
		minL = 0
		maxK = 0
		gapsList = []
		length = len(stringA)
		for i in range(length):
			if stringA[i] != stringB[i]:
				minL = minL + 1
		flag = 0
		for i in range(length):
			if stringA[i] != stringB[i]:
				if flag == 0:
					maxK = maxK + 1
				flag = 1
			else:
				flag = 0
		fl = 1
		glE = 0
		for i in range(length):
			if stringA[i] == stringB[i]:
				if fl == 0:
					glE = glE + 1
			else:
				if glE > 0:
					gapsList.append(glE)
				fl = 0
				glE = 0
		gapsList = sorted(gapsList)
		minCost = minL * maxK
		for i in range(len(gapsList)):
			minL = minL + gapsList[i]
			maxK = maxK - 1
			minCost = min(minCost, minL * maxK)
		stdout.write(str(minCost) + '\n')

	def __starting_point():
		main()
except Exception:
	pass
__starting_point()


from math import *
from itertools import *
t = int(input())
for i in range(t):
	s = list(input())
	r = list(input())
	n = len(s)
	l = [i for i in range(n) if s[i] != r[i]]
	m = len(l)
	if m == 1 or m == 0:
		print(m)
	else:
		l1 = l[m - 1] - l[0] + 1
		spaces = [l[i] - l[i - 1] - 1 for i in range(1, m)]
		spaces.sort(reverse=True)
		sol = l1
		for k in range(2, m + 1):
			l1 = l1 - spaces[k - 2]
			if k * l1 < sol:
				sol = k * l1
		print(sol)


for k in range(int(input())):
	ques = input()
	comp = input()
	temp = []
	zcount = []
	ocount = 0
	count = 0
	for i in range(len(ques)):
		if ques[i] != comp[i]:
			temp.append(1)
			ocount += 1
			if count != 0:
				zcount.append(count)
				count = 0
		elif ocount >= 1:
			temp.append(0)
			count += 1
	zcount = sorted(zcount)[::-1]
	zcount.insert(0, 0)
	temp = temp[:len(temp) - count]
	ans = ocount ** 2
	parts = 0
	num = len(temp)
	for i in range(len(zcount)):
		num = num - zcount[i]
		parts += 1
		ansp = parts * num
		ans = min(ans, ansp)
	print(ans)


for i in range(int(input())):
	s = input()
	r = input()
	n = len(r)
	gap = []
	t = 0
	l = 0
	for i in range(0, n):
		if s[i] == r[i]:
			t += 1
		else:
			gap.append(t)
			l += 1
			t = 0
	gap.append(t)
	gp = len(gap) - 1
	gap = gap[1:-1]
	gap.sort()
	x = l * gp
	for i in range(len(gap)):
		gp -= 1
		l += gap[i]
		y = gp * l
		if y < x:
			x = y
	print(min(x, n))


try:
	t = int(input())
	for v in range(t):
		s = input()
		r = input()
		i = 0
		prev = -1
		top = 0
		l = 0
		k = 0
		gap = []
		while i < len(s):
			if s[i] != r[i]:
				if prev != -1:
					gap.append(i - prev - 1)
					top += 1
				k += 1
				while i < len(s) and s[i] != r[i]:
					l += 1
					prev = i
					i += 1
			i += 1
		gap.sort()
		ans = k * l
		for i in range(top):
			l = l + gap[i]
			k = k - 1
			if ans > k * l:
				ans = k * l
		print(ans)
except:
	pass


for _ in range(int(input())):
	s = input()
	r = input()
	n = len(s)
	l = []
	(p, i, sum) = (0, 0, 0)
	while i < n:
		if s[i] == r[i]:
			p = 0
			while s[i] == r[i]:
				i += 1
				p += 1
				if i == n:
					break
			l.append(p)
		else:
			i += 1
	for i in l:
		sum += i
	k = len(l)
	if s[0] == r[0]:
		del l[0]
		k -= 1
	if s[n - 1] == r[n - 1] and k != 0:
		del l[k - 1]
		k -= 1
	l.sort()
	for i in range(1, k):
		l[i] += l[i - 1]
	count = (k + 1) * (n - sum)
	j = 0
	for i in range(k, 0, -1):
		if i * (n - sum + l[j]) < count:
			count = i * (n - sum + l[j])
		j += 1
	print(count)


for _ in range(int(input())):
	s1 = input()
	s2 = input()
	(i, j) = (0, len(s1) - 1)
	while i < len(s1) and s1[i] == s2[i]:
		i += 1
	while j >= 0 and s1[j] == s2[j]:
		j -= 1
	(l, k) = (0, 0)
	dif = [0]
	while i <= j:
		while s1[i] != s2[i]:
			i += 1
			l += 1
			if i == j + 1:
				break
		k += 1
		if i == j + 1:
			break
		while s1[i] == s2[i]:
			i += 1
			dif[-1] += 1
		dif.append(0)
	dif.sort()
	while dif[0] == 0:
		del dif[0]
		if dif == []:
			break
	ans = k * l
	for i in dif:
		k -= 1
		l += i
		ans = min(k * l, ans)
	print(ans)


from itertools import accumulate
from operator import sub
I = input
t = int(I())
for _ in range(t):
	s = ''.join(('* '[x != y] for (x, y) in zip(I(), I()))).strip('*')
	a = accumulate([len(s)] + sorted(map(len, s.split()), reverse=True), sub)
	print(min((k * l for (k, l) in enumerate(a, 1))))


for z in range(int(input())):
	l = input()
	r = input()
	di = []
	d = 0
	k = 0
	for i in range(len(l)):
		if l[i] == r[i]:
			d = d + 1
		else:
			di.append(d)
			k = k + 1
			d = 0
	di = di[1:]
	di.sort()
	ans = k * k
	l = k
	for ele in di:
		k = k - 1
		l = l + ele
		x = l * k
		ans = min(x, ans)
	print(ans)


t = int(input())
while t:
	gap = []
	l = 0
	k = 0
	s = input()
	r = input()
	flag = True
	new_flag = False
	gap_between = 0
	length = len(s)
	for i in range(length):
		if s[i] != r[i]:
			new_flag = True
		if new_flag == False:
			continue
		if s[i] != r[i]:
			if gap_between != 0:
				gap.append(gap_between)
				gap_between = 0
			l += 1
			if flag:
				k += 1
				flag = False
		else:
			flag = True
			gap_between += 1
	minOps = k * l
	if minOps == 0:
		print(0)
	else:
		gap.sort()
		for i in range(len(gap)):
			k -= 1
			if k <= 0:
				break
			l += gap[i]
			if l * k < minOps:
				minOps = l * k
		print(minOps)
	t -= 1


for _ in range(int(input())):
	s = list(input())
	r = list(input())
	l = []
	flag = 0
	eq = 0
	k = 0
	s_1 = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			if eq > 0 and flag == 1:
				l.append(eq)
				k += 1
			elif flag == 0:
				k += 1
			eq = 0
			flag = 1
			s_1 += 1
		else:
			eq += 1
	l.sort()
	res = 0
	res = k * s_1
	for i in range(len(l)):
		s_1 = s_1 + l[i]
		k = k - 1
		res = min(res, s_1 * k)
	print(res)


from itertools import accumulate
I = input
t = int(I())
for _ in range(t):
	s = ''.join(('* '[x != y] for (x, y) in zip(I(), I()))).strip('*')
	l = s.count(' ')
	s = s.split()
	a = accumulate([0] + sorted(map(len, s)))
	print(min(((len(s) - i) * (l + x) for (i, x) in enumerate(a, -1))))


for i in range(int(input())):
	s = input()
	s1 = input()
	(k, l, g) = (0, 0, 0)
	gp = []
	f = False
	for i in range(len(s)):
		if s[i] == s1[i]:
			if f:
				g += 1
		else:
			if not f:
				k += 1
			f = True
			l += 1
			if g > 0:
				k += 1
				gp.append(g)
				g = 0
	gp.sort()
	res = k * l
	for i in range(len(gp)):
		l += gp[i]
		k -= 1
		res = min(res, k * l)
	print(res)


T = int(input())
for _ in range(T):
	S = input()
	R = input()
	i = 0
	while i < len(R) and S[i] == R[i]:
		i += 1
	j = len(R) - 1
	while j >= 0 and S[j] == R[j]:
		j -= 1
	if i > j:
		print(0)
		continue
	P = []
	l = 0
	prev = -1
	for k in range(i, j + 1):
		if R[k] != S[k]:
			l += 1
			if prev != -1:
				P.append(k - prev)
				prev = -1
		elif prev == -1:
			prev = k
	P.sort()
	k = len(P) + 1
	ans = k * l
	for i in P:
		b = (k - 1) * (l + i)
		if b < ans:
			ans = b
		k -= 1
		l += i
	print(ans)


def value_l(l):
	k = 0
	for j in range(len(l)):
		k += l[j][1] - l[j][0] + 1
	return k
for _ in range(int(input())):
	s = input() + 'a'
	r = input() + 'a'
	i = 0
	l = []
	while i < len(s):
		if s[i] != r[i]:
			w = i
			while w < len(s):
				if s[w] == r[w]:
					l.append([i, w - 1])
					i = w - 1
					break
				w += 1
		i += 1
	o = []
	for i in range(len(l) - 1):
		o.append(l[i + 1][0] - l[i][1] - 1)
	o.sort()
	k = len(l)
	j = 0
	ans = k * value_l(l)
	f = 0
	h = value_l(l)
	while j < len(o):
		k = k - 1
		h += o[f]
		ans = min(ans, k * h)
		f += 1
		j += 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	t = input()
	diffcount = 0
	ans = []
	cont = False
	l = 0
	gap = 0
	k = 0
	for i in range(len(s)):
		if s[i] == t[i]:
			if cont:
				gap += 1
		else:
			if not cont:
				k += 1
			cont = True
			l += 1
			if gap > 0:
				ans.append(gap)
				gap = 0
				k += 1
	cs = k * l
	ans.sort()
	for i in range(len(ans)):
		k -= 1
		if k < 0:
			break
		l += ans[i]
		cs = min(cs, k * l)
	print(cs)


from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def powmod(a, b):
	a %= mod
	if a == 0:
		return 0
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b >>= 1
	return res

def main():
	for _ in range(ii()):
		s = si()
		r = si()
		a = []
		x = 0
		for i in range(1, len(s) + 1):
			if s[i - 1] != r[i - 1]:
				if x > 0:
					a.append(i - x - 1)
				x = i
		k = len(a) + 1
		ans = k * k
		a.sort()
		l = len(a) + 1
		if x == 0:
			ans = 0
		for i in a:
			k -= 1
			l += i
			ans = min(ans, k * l)
		print(ans)
main()


for _ in range(int(input())):
	s = input()
	r = input()
	(k, l, x) = (0, 0, 0)
	flg = 1
	ff = 0
	a = []
	for i in range(len(s)):
		if s[i] != r[i]:
			l += 1
			if flg:
				k += 1
			flg = 0
			ff = 1
			if x:
				a.append(x)
				x = 0
		elif ff:
			x += 1
			flg = 1
	a.sort()
	ans = k * l
	for i in a:
		l = l + i
		k -= 1
		ans = min(ans, k * l)
	print(ans)


for _ in range(int(input())):
	s = list(input())
	r = list(input())
	a = []
	for i in range(len(s)):
		if s[i] != r[i]:
			a.append(i)
	l = []
	for i in range(1, len(a)):
		l.append(a[i] - a[i - 1] - 1)
	l.sort()
	k = len(a)
	m = k
	y = 0
	ans = k * k
	for i in range(len(a) - 1, 0, -1):
		if y < len(l):
			m += l[y]
			ans = min(ans, i * m)
			y += 1
		else:
			break
	print(ans)


a = int(input())
for w in range(a):
	b = input()
	c = input()
	d = len(b)
	e = []
	r = 0
	t = 0
	p = 0
	i = 0
	z = 0
	y = 1
	for k in range(d):
		if b[k] != c[k]:
			r = r + 1
			t = 1
			if i != y:
				z = z + 1
				y = 0
			if p > 0:
				e.append(p)
				p = 0
		elif t == 1 and b[k] == c[k]:
			p = p + 1
			y = 1
	e.sort()
	n = r * z
	j = len(e)
	for it in range(j):
		r = r + e[it]
		z = z - 1
		if r * z < n:
			n = z * r
	print(n)


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	(n, index) = (len(s), 0)
	arr = []
	(l, k, previous) = (0, 0, -1)
	while index < n:
		if s[index] != r[index]:
			l += 1
			k += 1
			if previous != -1:
				arr.append(index - previous - 1)
			previous = index
		index += 1
	arr.sort()
	ans = l * k
	for i in arr:
		l += i
		k -= 1
		ans = min(ans, l * k)
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	r = input()
	if s == r:
		print(0)
		continue
	b = [True for x in range(len(s))]
	p = []
	for i in range(len(s)):
		if s[i] != r[i]:
			b[i] = False
	cnt = 0
	anytobechangedocuuredat = False
	d = True
	for i in range(len(s)):
		if b[i] == False:
			anytobechangedocuuredat = True
			if cnt > 0:
				p.append(cnt)
				cnt = 0
		elif anytobechangedocuuredat == True:
			if d == True:
				d = False
				cnt = 1
			else:
				cnt += 1
	p.sort()
	l = b.count(False)
	k = len(p) + 1
	ans = l * k
	for i in range(0, k - 1):
		l = l + p[i]
		k -= 1
		ans = min(ans, l * k)
	print(ans)


T = int(input())
for i in range(T):
	s = input()
	r = input()
	val = [i for i in range(len(s)) if s[i] != r[i]]
	a = [val[i + 1] - val[i] - 1 for i in range(len(val) - 1)]
	a.sort()
	(k, l) = (len(val), len(val))
	n = [k * l]
	for i in a:
		k -= 1
		l += i
		n.append(k * l)
	print(min(n))


t = int(input())
while t != 0:
	t = t - 1
	s = input()
	r = input()
	st = -1
	en = -2
	l = []
	n = len(s)
	for i in range(n):
		if s[i] != r[i]:
			st = en = i
			break
	while True:
		while i != n:
			if s[i] == r[i]:
				break
			en = i
			i += 1
		j = i
		while j != n:
			if s[j] != r[j]:
				break
			j += 1
		if j == n:
			break
		l.append(j - i)
		i = j
	l.sort(reverse=True)
	c = en - st + 1
	n = len(l)
	ans = c
	for i in range(n):
		if i > 0:
			l[i] += l[i - 1]
		ans = min(ans, (c - l[i]) * (i + 2))
	print(ans)


from sys import stdin
for _ in range(int(stdin.readline())):
	s = stdin.readline()
	r = stdin.readline()
	prev = cur = -2
	k = 0
	l = 0
	arr = []
	for i in range(len(r)):
		if s[i] != r[i]:
			l += 1
			prev = cur
			cur = i
			if cur - prev - 1 > 0:
				k += 1
				arr.append(cur - prev - 1)
	if prev == -2 and cur == -2:
		print('0')
		continue
	arr[0] = 10000000
	arr = sorted(arr)
	ans = k * l
	for i in range(len(arr) - 1):
		if ans > (k - 1) * (l + arr[i]) and k > 1:
			k -= 1
			l += arr[i]
			ans = k * l
		else:
			k -= 1
			l += arr[i]
	print(ans)


T = int(input())
while T:
	S = input()
	R = input()
	N = len(S)
	A = []
	if S == R:
		print('0')
	else:
		final = 0
		k = 0
		l = 1
		i = 0
		j = 0
		while S[i] == R[i]:
			i += 1
		var1 = i
		i += 1
		while i < N:
			if S[i] != R[i]:
				A.append(i - var1 - 1)
				var1 = i
				l += 1
			i += 1
		k = l
		final = k * l
		A.sort()
		i = 0
		for i in range(len(A)):
			k -= 1
			l += A[i]
			final = min(final, k * l)
		print(final)
	T -= 1


import sys
import math

def fout(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fin():
	return sys.stdin.readline().strip()
t = int(fin())
while t > 0:
	t -= 1
	s = fin()
	r = fin()
	un = isl = 0
	count = 0
	eqisl = []
	count2 = 0
	for i in range(len(r)):
		if s[i] == r[i]:
			if un == 0:
				continue
			count2 += 1
			if count > 0:
				isl += 1
				count = 0
		else:
			if count2 > 0:
				eqisl.append(count2)
				count2 = 0
			un += 1
			count += 1
	if count > 0:
		isl += 1
	eqisl.sort()
	ans = un * isl
	for i in range(len(eqisl)):
		un += eqisl[i]
		isl -= 1
		ans = min(ans, un * isl)
	print(ans)


for _ in range(int(input())):
	s = input()
	r = input()
	g = []
	(dg, gc, l, k) = (0, 0, 0, 0)
	for i in range(0, len(s)):
		if s[i] == r[i]:
			if dg:
				gc += 1
		else:
			if not dg:
				k += 1
			dg = 1
			l += 1
			if gc > 0:
				k += 1
				g.append(gc)
				gc = 0
	ans = k * l
	g.sort()
	for i in g:
		k -= 1
		l += i
		ans = min(ans, k * l)
	print(ans)


for _ in range(int(input())):
	s = list(input())
	r = list(input())
	n = len(s)
	notequal = []
	for i in range(n):
		if s[i] != r[i]:
			notequal.append(i)
	lenn = len(notequal)
	ans = lenn * lenn
	l = []
	for i in range(lenn - 1):
		l.append(notequal[i + 1] - notequal[i] - 1)
	l.sort()
	letters = lenn
	div = lenn
	for i in range(len(l)):
		div -= 1
		letters = letters + l[i]
		ans = min(ans, div * letters)
	print(ans)


for k in range(int(input())):
	ques = input()
	comp = input()
	zcount = []
	count = 0
	stat = False
	parts = 0
	changes = 0
	for i in range(len(ques)):
		if ques[i] != comp[i]:
			if not stat:
				parts += 1
			stat = True
			changes += 1
			if count > 0:
				zcount.append(count)
				count = 0
				parts += 1
		elif stat:
			count += 1
	zcount = sorted(zcount)
	ans = changes * parts
	for i in range(len(zcount)):
		changes = changes + zcount[i]
		parts -= 1
		ansp = parts * changes
		ans = min(ans, ansp)
	print(ans)


t = int(input())
while t:
	t -= 1
	s = input()
	r = input()
	k = 0
	l = 0
	gap = []
	g = 0
	flag = 0
	for i in range(len(s)):
		if s[i] != r[i]:
			l += 1
			if flag == 0:
				k += 1
			flag = 1
			if g > 0:
				k += 1
				gap.append(g)
				g = 0
		elif flag == 1:
			g += 1
	answer = k * l
	gap.sort()
	if k == 1:
		gap = []
	for i in range(len(gap)):
		l += gap[i]
		k -= 1
		answer = min(answer, k * l)
	print(answer)


T = int(input())
for i in range(T):
	S = input()
	R = input()
	cluster_list = []
	for i in range(len(S)):
		if len(cluster_list) == 0 or cluster_list[len(cluster_list) - 1][0] != (S[i] == R[i]):
			cluster_list.append([S[i] == R[i], 1])
		else:
			cluster_list[len(cluster_list) - 1][1] += 1
	t_cluster = []
	chr_len = 0
	clstr_len = 0
	for j in range(len(cluster_list)):
		if cluster_list[j][0] == True:
			if j != 0 and j != len(cluster_list) - 1:
				t_cluster.append((cluster_list[j][1], j))
		else:
			chr_len += cluster_list[j][1]
			clstr_len += 1
	t_cluster.sort()
	costs = [chr_len * clstr_len]
	for k in t_cluster:
		chr_len += k[0]
		clstr_len -= 1
		costs.append(chr_len * clstr_len)
	print(min(costs))


t = int(input())
while t:
	s = input()
	r = input()
	n = len(s)
	a = []
	a1 = 0
	a2 = 0
	k = l = 0
	for i in range(n):
		if s[i] != r[i]:
			if a2 > 0 and k > 0:
				a.append(a2)
				a2 = 0
			a2 = 0
			a1 += 1
		else:
			if a1 > 0:
				k = k + a1
				l = l + 1
				a1 = 0
			a2 += 1
	if a1 > 0:
		k = k + a1
		l = l + 1
	ans = l * k
	a.sort()
	for i in range(len(a)):
		k = k + a[i]
		l = l - 1
		if l == 0:
			break
		ans = min(ans, k * l)
	print(ans)
	t = t - 1


for _ in range(int(input())):
	S = input().strip()
	R = input().strip()
	if S == R:
		print(0)
		continue
	arr = []
	res = 0
	term = 0
	leftx = 1
	ind1 = 0
	while S[ind1] == R[ind1]:
		ind1 += 1
	pntc = ind1
	ind1 += 1
	n = len(S)
	while ind1 < n:
		if S[ind1] != R[ind1]:
			arr.append(ind1 - pntc - 1)
			pntc = ind1
			leftx += 1
		ind1 += 1
	term = leftx
	res = term * leftx
	arr = sorted(arr)
	for i in range(len(arr)):
		term -= 1
		leftx += arr[i]
		res = min(res, term * leftx)
	print(res)


t = int(input())
while t > 0:
	s = input()
	r = input()
	n = len(s)
	l = []
	for i in range(n):
		if s[i] != r[i]:
			l.append(i)
	if len(l) == 1 or len(l) == 0:
		print(len(l))
		t -= 1
		continue
	p = []
	for i in range(1, len(l)):
		p.append(l[i] - l[i - 1] - 1)
	k = len(l)
	flag = k
	ans = k * flag
	p = sorted(p)
	for i in range(len(p)):
		flag += p[i]
		if k > 0:
			k = k - 1
		ans = min(ans, flag * k)
	print(ans)
	t -= 1


for _ in range(int(input())):
	s = list(map(str, input()))
	r = list(map(str, input()))
	d = []
	flag = 0
	gl = 0
	k = 0
	l = 0
	for i in range(len(s)):
		if s[i] == r[i]:
			if flag == 1:
				gl += 1
		else:
			if flag == 0:
				k += 1
			flag = 1
			l += 1
			if gl > 0:
				k += 1
				d.append(gl)
				gl = 0
	d.sort()
	ans = k * l
	for i in range(len(d)):
		l = l + d[i]
		k -= 1
		ans = min(ans, k * l)
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	r = input()
	n = len(s)
	a = [i for i in range(n) if s[i] != r[i]]
	m = len(a)
	if m == 0:
		print(0)
	else:
		spaces = [a[i] - a[i - 1] - 1 for i in range(1, m) if a[i] - a[i - 1] - 1 != 0]
		spaces.sort()
		k = len(spaces) + 1
		l = a[-1] - a[0] + 1 - sum(spaces)
		sol = k * l
		i = 0
		while k != 1:
			l += spaces[i]
			i += 1
			k -= 1
			if l * k < sol:
				sol = l * k
		print(sol)


import sys
import math
from collections import defaultdict
mod = 1000000007
T = 1
T = int(sys.stdin.readline())
for _ in range(T):
	s = input()
	r = input()
	(k, l, x) = (0, 0, 0)
	flg = 1
	ff = 0
	a = []
	for i in range(len(s)):
		if s[i] != r[i]:
			l += 1
			if flg:
				k += 1
			flg = 0
			ff = 1
			if x:
				a.append(x)
				x = 0
		elif ff:
			x += 1
			flg = 1
	a.sort()
	ans = k * l
	for i in a:
		l = l + i
		k -= 1
		ans = min(ans, k * l)
	print(ans)


import math
import numpy as np
t = int(input())
for i in range(t):
	arr = list(input())
	arr2 = list(input())
	first = len(arr)
	last = -1
	for i in range(len(arr)):
		if arr[i] != arr2[i]:
			if first > i:
				first = i
			if last < i:
				last = i
	arr = arr[first:last + 1]
	arr2 = arr2[first:last + 1]
	n = len(arr)
	cnt = 0
	a = []
	first = n
	last = 0
	for i in range(n):
		if arr[i] == arr2[i]:
			cnt = cnt + 1
			if i == n - 1:
				a.append(cnt)
		elif cnt != 0:
			a.append(cnt)
			cnt = 0
	a.sort()
	a.append(0)
	p = n
	ans = []
	cnt = 1
	for i in a[::-1]:
		p = p - i
		ans.append(p * cnt)
		cnt = cnt + 1
	print(min(ans))


from itertools import accumulate
I = input
t = int(I())
for _ in range(t):
	s = ''.join(('* '[x != y] for (x, y) in zip(I(), I()))).strip('*')
	a = accumulate([-len(s)] + sorted(map(len, s.split()), reverse=True))
	print(-max((k * minus_l for (k, minus_l) in enumerate(a, 1))))


for _ in range(int(input())):
	a = input()
	b = input()
	n = len(a)
	x = n
	for i in range(n):
		if a[i] != b[i]:
			x = i
			break
	l = []
	count = 0
	xx = 0
	for i in range(x, n):
		if a[i] == b[i]:
			count += 1
		else:
			xx += 1
			if count != 0:
				l.append(count)
				count = 0
	l.sort()
	x = len(l) + 1
	mini = x * xx
	while len(l) != 0:
		xx += l[0]
		x -= 1
		l.pop(0)
		mini = min(mini, xx * x)
	print(mini)


for _ in range(int(input())):
	a = str(input())
	b = str(input())
	if a == b:
		print(0)
		continue
	indices = [i for i in range(len(a)) if a[i] != b[i]]
	n = len(indices)
	if n == 1:
		print(1)
		continue
	temp = []
	for k in range(n - 1):
		temp.append(indices[k + 1] - indices[k] - 1)
	temp.sort(reverse=True)
	ans = indices[-1] - indices[0] + 1
	length = ans
	ind = 0
	for k in range(2, n + 1):
		length = length - temp[ind]
		ans = min(ans, k * length)
		ind += 1
	print(ans)