Anna and the palindrome#1986

Anna and the palindrome

1 second
64 megabytes
Medium

Anna learned at school what a palindrome is. Later, while visiting Ben, she took his blocks with lowercase Latin letters on them and began playing a game she invented on her way. In this game, she randomly formed a word (an "abracadabra") using any number of cubes, and then tried to turn this word into a palindrome.

Since Anna is still small, the rules of her game specify that she can only swap two adjacent cubes during play. Sometimes she managed to create a palindrome this way, and sometimes she did not, in which case she would exclaim in surprise: "Ooops..."

Your task is to determine the minimum number of adjacent swaps required for Anna to obtain a palindrome in each case, or to determine if it is impossible.

Input

The first line contains a natural number (T \leq 150) — the number of test cases. The following lines each contain the initial sequence made from cubes. The sequence length does not exceed .

Output

For each test case, output the minimum number of moves needed for Anna to obtain a palindrome, or if it is not possible, output "Ooops..." (without quotes).

Examples

Example 1

Loading
Loading