Bajtek, thanks to attending a computer science club, learned what a palindrome is. A palindrome is a word that reads the same from left to right as it does from right to left. For example, the words "oko", "kajak", "kobyłamamałybok", and "ababbaba" are palindromes, while the words "kajaki", "zoo", "alamakota", and "abaababa" are not.

Excited by his new knowledge, the boy quickly opened his notepad (not a notebook, but a program) and wrote down a word consisting of the letters 'a' and 'b'. After a moment of reflection, however, it dawned on him that his word might not necessarily be a palindrome. He decided to fix that! In one second, the boy can choose two adjacent letters and swap them. Will he be able to make his word a palindrome by performing a sequence of such moves (or by doing nothing)? If so, what is the minimum number of seconds such changes will take? Help him and write a program that calculates this!

Input

The single line of input contains a non-empty word written in Bajtek's notepad. The word can only contain the characters 'a' and 'b', and its length will not exceed 200,000 characters.

Output

The output should contain a single integer representing the minimum number of seconds needed to change the word from Bajtek's notepad into a palindrome. If it is not possible, the number -1 should be output instead.

Examples

Input 1

abbaaab

Output 1

2

Note 1

In the first example test, Bajtek can (for example) perform the sequence of changes abbaaab → babaaab → baabaab, which correctly turns his word into a palindrome, taking him two seconds. It can be shown that it is impossible to turn his word into a palindrome faster.

Input 2

ab

Output 2

-1

Note 2

In the second example test, Bajtek's word can be in the form ab or ba. Neither of these words is a palindrome, so the boy will not be able to complete the task.