Papple Sort

You are given a string S consisting of lowercase English letters. Determine whether we can turn S into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.

Constraints

• 1 \leq |S| \leq 2 × 10^5
• S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If we cannot turn S into a palindrome, print -1. Otherwise, print the minimum required number of operations.

Examples

Input

eel

Output

1

Input

ataatmma

Output

4

Input

snuke

Output

-1

inputFormat

Input

Input is given from Standard Input in the following format:

S

outputFormat

Output

If we cannot turn S into a palindrome, print -1. Otherwise, print the minimum required number of operations.

Examples

Input

eel

Output

1

Input

ataatmma

Output

4

Input

snuke

Output

-1

样例

snuke

-1