Buri Shabu Shabu Buri Club

This is a news report. As the spread of COVID-19 pushes more people to look for better meals outside restaurants, one club has drawn attention.

Its name is Buri Shabu Shabu Buri Club. A reporter visited a group in Tokyo that works on this new activity.

In an apartment in Shibuya Ward, young men and women from their teens to their thirties gather around a pot. "Can this crab be eaten now?" "Oh, it really can." From the outside, it looks like an ordinary crab hot pot. It does not even seem to contain yellowtail (buri)...?

The reporter asked the man who leads the group. ICPC-JAG (International Collegiate Programming Contest Japanese Alumni Group) representative N: "Today is the celebration after the ICPC mock domestic qualifier." Reporter: "Then what exactly is Buri Shabu Shabu Buri Club?" N: "Doesn't Buri Shabu Shabu Buri sound a bit like a palindrome?" Reporter: "P-palindrome...?" N: "A palindrome is a text that reads the same forward and backward. Something palindrome-like is, well..."

You, a JAG member who was listening to this conversation while picking at the crab hot pot, thought that writing a program to judge how palindrome-like a string is might help the reporter. Here, the palindrome-likeness of a string is defined as follows.

• Take the second half of the string (excluding the middle character when the length is odd). Choose any number, zero or more, of intervals that do not overlap, and reverse the substring of each chosen interval so that the whole string becomes a palindrome. If at least one way of choosing intervals makes the string a palindrome, the palindrome-likeness is the minimum, over those choices, of the sum of the squares of the interval lengths. If no way of choosing intervals makes it a palindrome, the palindrome-likeness is -1. A string $S = S_1 S_2 ... S_n$ of length $n$ is a palindrome only when $S_i = S_{n+1-i}$ holds for every $i = 1, ..., n$.

The input consists of at most 50 datasets. Each dataset is given in the following format.

S

$S$ is a string of lowercase English letters with $1 ≤ |S| ≤ 20000$.

The input ends with a line containing only one character, #.

For each dataset, print the palindrome-likeness of the string $S$ on one line.