Some data scientists are building a utility to analyze palindromic trends in the dna sequencing of a string. The palindrome transformation cost of a string is defined as the minimum number of characters that need to be changed in it so that it can be rearranged to form a palindrome. For example, the palindrome transformation cost of the string "aabcd" is $1$ as we can change the last character d to c so that the string becomes "aabcc" that can be rearranged to "acbca" which is a palindrome. Given string dna, find the total sum of palindrome transformation cost of all the substrings of the given string. Note, a palindrome is a sequence that reads the same backwards as forwards.

Example

Suppose dna $=$ "abca", substrings of dna with their costs are$-$

$"$a$",$b$,$c$,$d$$ with cost $=0$

$$ab$,$ cost $=1,$ we can change $\text{'}$b$\text{'}$ to $$a$\text{'}$ and it becomes $$aa$$ which is a palindrome.

$$ "abc$,$ cost $=1,$ we can change $\text{'}$b$\text{'}$ to $\text{'}$c$\text{'}$ and it can be rearranged to "cac" which is a palindrome.

$$abca$,$ cost $=1.$ we can change $\text{'}$b$\text{'}$ to $\text{'}$c$\text{'}$ and it becomes "acca" which IS a palindrome.

$"$bc$".$ cost$=1,$ we can change b$\text{'}$ to $\text{'}$c$\text{'}$ and it becomes $$cc$"$ which is a palindrome.

$$ "bca", cost$=1,$ we can change $$c$\text{'}$ to $$a$\text{'}$ and it can be rearranged to "aba" which is a palindrome.

$$ca$$ cost $=1.$ we can change $$c$\text{'}$ to $\text{'}$a$\text{'}$ and it becomes $"$aa$"$ which is a palindrome.

Hence the answer is $1+1+1+1+1+1=6.$

Function Description

Complete the function getTotalPalindromeTransformationCost in the editor below. The function

returns me total sum of palindrome transformation costs across all substrings,

getTotalPalindromeTransformationCost has the following parameter:

dna: A string

Constraints : $1<=|$dna$|<=2$e$5$

Sample Input For Custom Testing

acbaed

Sample Output

$19$

Explanation

Given dna $=$ "acbaed",

$$a$,$c$,$b$,$a$,$d$,$e$$ have cost $=0$

$$ All substrings of length $2$ i$.$e $$ac$,"$cb$","$ba$","$ae$",$ed$$ have cost$=1.$ we can change either of the character to other.

$$acb$".$cba$".$ "bae". "aed" have cost $=1.$ we can change last character to first character in each of them.

$$acba$"$ has cost $=1,$ we can change $\text{'}$b$\text{'}$ to $$a$$

$$ "acbae$$ has cost $=1,$ we can change $$c$\text{'}$ to $\text{'}$e$\text{'}$ and it can be rearranged to "aebea" which is a palindrome.

$$ "acbaed" has cost$=2,$ we can change $$c$\text{'}$ to $$e$\text{'}$ and $$b$$ to $$d$,$ then it c$$n be rearranged to "aeddea" which is a palindrome. Similarly, "cbae$,$ "baed" and "cbaed" have cost $=2.$

Hence the answer is $(5*1)+(4*1)+1+1+(4*2)=19$