Minimum Swaps to Palindrome

You are given a string s consisting of lowercase letters. Your task is to transform the string into a palindrome by performing a series of operations. In one operation, you are allowed to swap two adjacent characters.

A palindrome is a string that reads the same forwards and backwards. More formally, a string s of length n is a palindrome if:

\(s[i] = s[n-i-1]\) for \(0 \le i < n\).

It is not always possible to form a palindrome. A necessary condition is that at most one character appears an odd number of times. In mathematical terms, if \(count(c)\) represents the frequency of character \(c\) in s, then the string can form a palindrome only if:

\(\#\{c : count(c) \mod 2 \neq 0\} \leq 1\)

If it is possible, determine the minimum number of adjacent swap operations required to transform the string into a palindrome. If it is impossible, output -1.

You will be given T test cases. For each test case, output the answer on a new line.

inputFormat

The first line of input contains an integer T (1 ≤ T ≤ 50), the number of test cases. Each of the following T lines contains a single string s consisting of lowercase letters. The length of each string is at least 1 and at most 1000.

Example:

2
mamad
asflkj

outputFormat

For each test case, output a single integer on a new line representing the minimum number of adjacent swaps required to transform the string into a palindrome. If it is impossible, output -1.

Example:

3
-1

## sample

2
mamad
asflkj

3
-1

</p>