Char Swap

Problem

Given a string S of even length. You can swap two adjacent characters in the string S as many times as you like. How many operations do we need to do to make the string S a palindrome? If it is not possible to make a palindrome, output -1.

Constraints

• 2 ≤ | S | ≤ 4 x 105
• All strings are composed of lowercase letters
• String length is even

Input

The input is given in the following format.

S

The string S is given on one line.

Output

Outputs the minimum number of operations to make the character string S a palindrome on one line. If it is not possible to make a palindrome, output -1 on one line instead.

Examples

Input

acca

Output

0

Input

acpcacpc

Output

3

Input

aizu

Output

-1

inputFormat

outputFormat

output -1.

Constraints

• 2 ≤ | S | ≤ 4 x 105
• All strings are composed of lowercase letters
• String length is even

Input

The input is given in the following format.

S

The string S is given on one line.

Output

Outputs the minimum number of operations to make the character string S a palindrome on one line. If it is not possible to make a palindrome, output -1 on one line instead.

Examples

Input

acca

Output

0

Input

acpcacpc

Output

3

Input

aizu

Output

-1

样例

acca

0