Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Watson gives to Sherlock two strings S_{1} and S_{2} consisting of uppercase English alphabets. Next he wants Sherlock to build a flower in the following way:

He puts both strings perpendicular to each other in such a way that they overlap at the same character. For example, if he has two strings "ABCDEF" and "XXBCZQ", one possible way to make a flower is:
   
Length of petals in the above flower are 2, 2, 3 and 3.
A flower's ugliness is sum of absolute difference of adjacent petal lengths i.e. i.e. if adjacent petal lengths are L_{1}, L_{2}, L_{3}, L_{4}, then ugliness of flower is |L_{1} - L_{2}| + |L_{2} - L_{3}| + |L_{3} - L_{4}| + |L_{4} - L_{1}|. 

Sherlock wants to find minimum value of ugliness if we consider all possible flower configurations. Note that a configuration is valid even if any of the petal length is 0.

------ Input ------ 

First line contains T, number of test cases. Each test case consists of string S_{1} in one line followed by string S_{2} in the next line. It is guaranteed that there exists at least one possible way to make a flower.
  
------ Output ------ 

For each test case, output in one line the required answer.

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

$1 ≤ T ≤ 10$
$1 ≤ length(S_{1}), length(S_{2}) ≤ 10^{5}$

----- Sample Input 1 ------ 
2
ABCDE
XXBCZQ
BBB
BBBBBB
----- Sample Output 1 ------ 
2
6
----- explanation 1 ------ 

Test case 1:
If we keep the configuration shown in statement, the ugliness is 2, which is minimum possible.

Test case 2:
One of the best configurations is

B 
B B B  B  B B
B

where petal lengths are 1, 3, 1, 2.

Source: codechef | Difficulty: HARD
Tags: String algorithms

Sorting

Complete search

Mathematics

Data structures


Solutions:
T = input()
T = int(T)

def compute_ugliness(i, j, n1, n2):
	(L1, L2, L3, L4) = (i, n1 - i - 1, j, n2 - j - 1)
	return abs(L1 - L3) + abs(L1 - L4) + abs(L2 - L3) + abs(L2 - L4)

def optimal_sol(S1, S2):
	(mid2, min_ugliness) = (len(S2) // 2, 1000000.0)
	char_to_ids = {}
	for (j, char) in enumerate(s2):
		if char in char_to_ids and abs(mid2 - j) > abs(mid2 - char_to_ids[char]):
			continue
		char_to_ids[char] = j
	for (i, char) in enumerate(s1):
		if char in char_to_ids:
			j = char_to_ids[char]
			min_ugliness = min(min_ugliness, compute_ugliness(i, j, len(S1), len(S2)))
	return min_ugliness if min_ugliness < 1000000.0 else -1
result = []
for i in range(T):
	s1 = input()
	s2 = input()
	result.append(optimal_sol(s1, s2))
for i in result:
	print(i)


T = input()
T = int(T)

def find_index(a, mid):
	(l, r) = (0, len(a) - 1)
	cur_min = 99999
	rs = -1
	while l <= r:
		cur_mid = int((l + r) / 2)
		if abs(a[cur_mid] - mid) < cur_min:
			cur_min = abs(a[cur_mid] - mid)
			rs = cur_mid
		if a[cur_mid] > mid:
			r = cur_mid - 1
		else:
			l = cur_mid + 1
	return a[rs]

def sol(s1, s2):
	n1 = len(s1)
	n2 = len(s2)
	mid1 = int(n1 / 2)
	mid2 = int(n2 / 2)
	char_to_ids = {}
	for (idx, char) in enumerate(s2):
		if char in char_to_ids:
			if abs(mid2 - idx) < abs(mid2 - char_to_ids[char]):
				char_to_ids[char] = idx
		else:
			char_to_ids[char] = idx
	m = 9999999
	for (idx, char) in enumerate(s1):
		L1 = idx
		L2 = n1 - idx - 1
		if char in char_to_ids:
			j = char_to_ids[char]
			L3 = j
			L4 = n2 - j - 1
			m = min(m, abs(L1 - L3) + abs(L1 - L4) + abs(L2 - L3) + abs(L2 - L4))
	return m
result = []
for i in range(T):
	s1 = input()
	s2 = input()
	result.append(sol(s1, s2))
for i in result:
	print(i)


from collections import defaultdict
for _ in range(int(input())):
	s1 = input()
	s2 = input()
	ms = defaultdict(list)
	(l, r) = (0, len(s1) - 1)
	while l <= r:
		if s1[l] == s1[r]:
			ms[s1[l]] = [l, r]
		else:
			ms[s1[l]] = [l, r]
			ms[s1[r]] = [r, l]
		l += 1
		r -= 1
	ugly = 10000000000.0
	n = len(s2) - 1
	for i in range(n + 1):
		if s2[i] in ms:
			u = abs(ms[s2[i]][0] - i) + abs(ms[s2[i]][1] - i) + abs(ms[s2[i]][0] - (n - i)) + abs(ms[s2[i]][1] - (n - i))
			ugly = min(ugly, u)
	print(ugly)


from sys import stdin
import math
strA = [-1 for i in range(27)]
strB = [-1 for i in range(27)]

def clear():
	for i in range(27):
		strA[i] = strB[i] = -1

def check(Ln_Lm):
	if Ln_Lm < 0:
		return -1 * Ln_Lm
	return Ln_Lm

def calcUgly(L1, L2, L3, L4):
	L1_L2 = L1 - L2
	L2_L3 = L2 - L3
	L3_L4 = L3 - L4
	L4_L1 = L4 - L1
	ugliness = math.fabs(L1_L2) + math.fabs(L2_L3) + math.fabs(L3_L4) + math.fabs(L4_L1)
	return int(ugliness)

def parseString(str, arr, length):
	ind1 = ind2 = length // 2
	while ind1 >= 0 and ind2 < length:
		if arr[ord(str[ind1]) - ord('A')] == -1:
			arr[ord(str[ind1]) - ord('A')] = ind1
		if arr[ord(str[ind2]) - ord('A')] == -1:
			arr[ord(str[ind2]) - ord('A')] = ind2
		ind1 -= 1
		ind2 += 1
	while ind1 >= 0:
		if arr[ord(str[ind1]) - ord('A')] == -1:
			arr[ord(str[ind1]) - ord('A')] = ind1
		ind1 -= 1
	while ind2 < length:
		if arr[ord(str[ind2]) - ord('A')] == -1:
			arr[ord(str[ind2]) - ord('A')] = ind2
		ind2 += 1

def solve():
	T = int(stdin.readline().strip())
	for t in range(T):
		S1 = stdin.readline().strip()
		S2 = stdin.readline().strip()
		len1 = len(S1)
		len2 = len(S2)
		parseString(S1, strA, len1)
		parseString(S2, strB, len2)
		minUgly = len1 + len2
		for i in range(26):
			if strA[i] != -1 and strB[i] != -1:
				currUgly = calcUgly(strA[i], len2 - strB[i] - 1, len1 - strA[i] - 1, strB[i])
				if currUgly < minUgly:
					minUgly = currUgly
		print(minUgly)
		clear()
solve()


import math

def midpoint(a):
	if a % 2 == 0:
		return a // 2 - 1
	else:
		return (a + 1) // 2 - 1

def count_petal(a, a_mid, b, b_mid):
	l1 = a_mid - 1
	l3 = len(a) - a_mid
	l4 = b_mid - 1
	l2 = len(b) - b_mid
	return abs(l1 - l2) + abs(l2 - l3) + abs(l3 - l4) + abs(l4 - l1)
t = int(input())
while t:
	a = input()
	b = input()
	best = []
	a_mid = midpoint(len(a))
	b_mid = midpoint(len(b))
	if a[a_mid] == b[b_mid]:
		print(count_petal(a, a_mid + 1, b, b_mid + 1))
	else:
		a_set = set(a)
		b_set = set(b)
		a_dict = dict()
		b_dict = dict()
		inset = a_set & b_set
		for i in inset:
			a_dict[i] = (1000000, 1000000)
			b_dict[i] = (1000000, 1000000)
		for (i, j) in enumerate(a):
			if j in inset:
				if abs(i - a_mid) <= a_dict[j][0]:
					a_dict[j] = (abs(i - a_mid), i)
		for (i, j) in enumerate(b):
			if j in inset:
				if abs(i - b_mid) <= b_dict[j][0]:
					b_dict[j] = (abs(i - b_mid), i)
		minimum = 1000000
		for i in inset:
			minimum = min(minimum, count_petal(a, a_dict[i][1] + 1, b, b_dict[i][1] + 1))
		print(minimum)
	t -= 1


import sys

def dis(n, i):
	if n % 2 == 0:
		r1 = abs(i - n // 2)
		r2 = abs(i - n // 2 + 1)
		return min(r1, r2)
	else:
		return abs(i - n // 2)
for cases in range(int(input())):
	s1 = input()
	s2 = input()
	d1 = dict()
	d2 = dict()
	(n1, n2) = (len(s1), len(s2))
	for i in range(n1):
		ind = ord(s1[i]) - 65
		if ind in d1:
			d1[ind] = min(dis(n1, i), d1[ind])
		else:
			d1[ind] = dis(n1, i)
	for i in range(n2):
		ind = ord(s2[i]) - 65
		if ind in d2:
			d2[ind] = min(dis(n2, i), d2[ind])
		else:
			d2[ind] = dis(n2, i)
	min1 = sys.maxsize
	for i in range(26):
		if i in d1 and i in d2:
			c1 = n1 // 2 + d1[i]
			c2 = n2 // 2 + d2[i]
			l1 = c1
			l3 = n1 - 1 - c1
			l2 = c2
			l4 = n2 - 1 - c2
			val = abs(l1 - l2) + abs(l2 - l3) + abs(l3 - l4) + abs(l4 - l1)
			if val < min1:
				min1 = val
	print(min1)


T = int(input())
for t in range(T):
	S1 = list(input().strip())
	S2 = list(input().strip())
	n1 = len(S1)
	n2 = len(S2)
	c1 = [-1] * 26
	i = 0
	while i < (n1 + 1) // 2:
		c1[ord(S1[i]) - 65] = i
		c1[ord(S1[n1 - i - 1]) - 65] = i
		i += 1
	c2 = [-1] * 26
	i = 0
	while i < (n2 + 1) // 2:
		c2[ord(S2[i]) - 65] = i
		c2[ord(S2[n2 - i - 1]) - 65] = i
		i += 1
	close = 1000000000.0
	for i in range(26):
		L1 = c1[i]
		L2 = c2[i]
		if L1 == -1 or L2 == -1:
			continue
		L3 = n1 - c1[i] - 1
		L4 = n2 - c2[i] - 1
		close = min(abs(L1 - L2) + abs(L2 - L3) + abs(L3 - L4) + abs(L4 - L1), close)
	print(close)


t = int(input())
for i in range(t):
	s = input()
	r = input()
	tab1 = {}
	tab2 = {}
	for j in range(26):
		tab1[j] = -1
		tab2[j] = -1
	l1 = len(s)
	l2 = len(r)
	for j in range(l1):
		u = tab1[ord(s[j]) - ord('A')]
		if abs(j - l1 / 2) < abs(u - l1 / 2):
			tab1[ord(s[j]) - ord('A')] = j
	for j in range(l2):
		u = tab2[ord(r[j]) - ord('A')]
		if abs(j - l2 / 2) < abs(u - l2 / 2):
			tab2[ord(r[j]) - ord('A')] = j
	m = 500000
	for j in range(26):
		d = tab1[j]
		d1 = tab2[j]
		if d + 1 == 0 or d1 + 1 == 0:
			continue
		q1 = d
		q2 = d1
		q3 = l1 - 1 - d
		q4 = l2 - 1 - d1
		z = abs(q1 - q2) + abs(q2 - q3) + abs(q3 - q4) + abs(q4 - q1)
		m = min(z, m)
	print(m)