In the last ACM training, Dima learned about palindromic strings, strings that read the same way when they're reversed (e.g. AABAA). Excited about what she learned, Dima decided to give her friend Rund a challenge:  

Let's define an operation as increasing or decreasing a letter of a string (for example, in 1 operation, AAB can be turned into AAC or AAA).  

Given a string, what's the minimum number of operations that can be applied to the string, such that every possible substring of that string is a palindrome?

Since Rund is not very good at handling strings, she asked you to help her as Dima is going to treat her to mansaf if she solves the challenge.

Note that a substring is a contiguous sequence of characters within a string. For instance,  "MAN" and "AF" are substrings of the string "MANSAF", while "MF and "AS" are not.

The first and only line will contain as string $s$ consisting of lowercase English characters $(1 \le |s| \le 10^5)$, where $|s|$ denotes the length of the string $s$. 

Output a single integer, the minimum number of operations needed so that every substring in $s$ is a palindrome.