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: interview

Starter code:

Solutions:
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)

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)

import sys
import math
# from collections import defaultdict, deque

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 #unequal
 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()
 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
 # print(groups)
 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)

# P.S.: I understood the solution using the code of https://www.codechef.com    /viewsolution/33283413 
# the user's name is kush_07(thanks to him), but it took me some time to figure     it out so i
# have written some comments which might help you if you by any chance arrive at     the solution.
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]:
   # When the group/array is not the first array to have different                 characters 
   # this is identified using the flag variable
   # as we don't need the elements which were before the first                 different
   # subarray but only need the elements between the different                 subarrays after
   # the first subarray having different characters (subarrays here                 refer to 'islands' 
   # mentioned in the tutorial)
   if eq>0 and flag==1:
    l.append(eq)
    k+=1
   # we are not appending the equal elements before this as this is the                 first subarray with
   # different characters (flag==0) but we still need to count it as                 one operation so k+=1
   elif flag==0:
    k+=1
   eq=0
   flag=1
   # Number of characters that would require replacing
   s_1+=1
  else:
   # Counting the same characters 
   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)
   
   


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

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
  else:
   if c!=0:
    gap.append(c)
    c=0
 #print(gap,k,l)
 gap.sort()
 for i in gap:
  k-=1
  l+=i
  ans=min(ans,k*l)
 print(ans)


# cook your dish here
test=int(input())
for _ in range(test):
 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)
 # print(mismatches)
 # print(e_islands)
 # print(u_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 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)
 # print(mismatches)
 # print(e_islands)
 # print(u_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)


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 is positions where stringA[i]!=stringB[i]
  minL=0
  maxK=0
  #gapsList that contains ranges where elements are equal
  gapsList=[]
  length=len(stringA)
  #finding minL
  for i in range(length):
   if stringA[i]!=stringB[i]:
    minL=minL+1
  #A=abbbbaabb
  #B=aaaaaaaaa
  #finding maxK
  flag=0
  for i in range(length):
   if stringA[i]!=stringB[i]:
    if flag==0:
     maxK=maxK+1
    flag=1
   else:
    flag=0
  #finding gapsList
  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)
  #Calculating minCost
  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()

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)
 # print(mismatches)
 # print(e_islands)
 # print(u_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)


# cook your dish here
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;


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))


# cook your dish here
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 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)

# cook your dish here
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)

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 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
  else:
   if 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)

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) 

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)

# cook your dish here
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
  else:
   if 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 _ 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
  else:
   if 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 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))