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$.
# 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)
   
   

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