Masha and the palindrome
Mache at school told me that is a palindrome. And then came a visit to Misha, she took his cubes, which depicts small latin letters and started playing with herself in the game, invented by road. The essence of the game was that it was random word "abracadabra" of an arbitrary number of cubes, and then tried to get out the word palindrome.
Since Masha is still small, it is prudent in the rules of the game pointed out that during the game can be swapped only two adjacent cubes. Of course, sometimes it is worked and sometimes did - no, and then she surprised pronounced "Ooops...".
Your task is to find the minimum number of permutations of the dice, the right to Masha for the next palindrome.
Input
The first line indicates a positive number - the number of test cases T (T ≤ 150). In the following T lines of the original machine is given another sequence of blocks. Sequence length does not exceed 100.
Output
Withdraw the required minimum number of moves needed to Masha for palindrome, or in case of failure to do so astonished by Masha phrase "Ooops..." (without the quotes).