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

You are given a string $S$ of lowercase English letters with length $N$. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by $X$.

Next, consider the number of pairs of indices $(i, j)$ in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that $1 ≤ i < j ≤ N$ and $S_{i} < S_{j}$. Let's denote it by $Y$.

Find the minimum possible value of $X+Y$.

------  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 and only line of each test case contains a single string $S$. 

------  Output ------
For each test case, print a single line containing one integer — the minimum value of $X+Y$.

------  Constraints  ------
$1 ≤ T ≤ 20$
$1 ≤ N ≤ 10^{5}$
$S$ contains only lowercase English letters

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ N ≤ 50$

Subtask #2 (20 points): $1 ≤ N ≤ 250$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
3
abcd
dbca
dcba
----- Sample Output 1 ------ 
6
1
0

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Implementation


Solutions:
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
indices = {letter: letters.index(letter) for letter in letters}
for _ in range(int(input())):
	count = [0 for i in range(26)]
	ans = 0
	arr = list(input())
	for let in arr[::-1]:
		if let == 'z':
			count[-1] += 1
			continue
		else:
			count[indices[let]] += 1
			ans += sum(count[indices[let] + 1:])
	fin = ans
	tobeinc = []
	for let in letters[:-1]:
		if count[indices[let]] != 0:
			tobeinc += [arr.index(let)]
	for index in tobeinc:
		current = ans
		countl = [0 for i in range(26)]
		countr = [0 for i in range(26)]
		for i in range(index):
			countl[indices[arr[i]]] += 1
		for i in range(index + 1, len(arr)):
			countr[indices[arr[i]]] += 1
		current = current - sum(countl[:indices[arr[index]]]) - sum(countr[indices[arr[index]] + 1:])
		for i in range(indices[arr[index]] + 1, 26):
			new = current + sum(countl[:i]) + sum(countr[i + 1:]) + abs(indices[arr[index]] - i)
			fin = min(fin, new)
	tobedic = []
	for let in letters[1:]:
		if count[indices[let]] != 0:
			tobedic += [len(arr) - 1 - arr[::-1].index(let)]
	for index in tobedic:
		current = ans
		countl = [0 for i in range(26)]
		countr = [0 for i in range(26)]
		for i in range(index):
			countl[indices[arr[i]]] += 1
		for i in range(index + 1, len(arr)):
			countr[indices[arr[i]]] += 1
		current = current - sum(countl[:indices[arr[index]]]) - sum(countr[indices[arr[index]] + 1:])
		for i in range(0, indices[arr[index]]):
			new = current + sum(countl[:i]) + sum(countr[i + 1:]) + abs(indices[arr[index]] - i)
			fin = min(fin, new)
	print(fin)