Маша и палиндром
Маше в школе рассказали, что такое палиндром. И вот придя в гости к Мише, она достала его кубики, на которых изображены маленькие буквы английского алфавита и начала играть сама с собой в игру, придуманную по дороге. Суть игры состояла в том, что она наугад составляла слово-"абракадабру" из произвольного числа кубиков, а потом пробовала получить из этого слова палиндром.
Так как Маша ещё маленькая, то она предусмотрительно в правилах игры указала, что во время игры можно менять местами только два соседних кубика. Естественно, иногда у неё это получалось, а иногда - нет, и тогда она удивлённо произносила "Ooops...".
Ваша задача найти минимальное количество перестановок кубиков, нужное Маше для получения очередного палиндрома.
Входные данные
В первой строке указано натуральное число - количество тестовых случаев T (T ≤ 150). В последующих T строках задана очередная исходная Машина последовательность из кубиков. Длина последовательности не превышает 100.
Выходные данные
Вывести искомое минимальное количество ходов, нужных Маше для получения палиндрома, либо, в случае невозможности сделать это, удивлённую фразу Маши "Ooops..." (без кавычек).