Məsələlər
Маша и палиндром
Маша и палиндром
Маше в школе рассказали, что такое палиндром. И вот придя в гости к Мише, она достала его кубики, на которых изображены маленькие буквы английского алфавита и начала играть сама с собой в игру, придуманную по дороге. Суть игры состояла в том, что она наугад составляла слово-"абракадабру" из произвольного числа кубиков, а потом пробовала получить из этого слова палиндром.
Так как Маша ещё маленькая, то она предусмотрительно в правилах игры указала, что во время игры можно менять местами только два соседних кубика. Естественно, иногда у неё это получалось, а иногда - нет, и тогда она удивлённо произносила "\textbf{Ooops...}".
Ваша задача найти минимальное количество перестановок кубиков, нужное Маше для получения очередного палиндрома.
\InputFile
В первой строке указано натуральное число - количество тестовых случаев \textbf{T} (\textbf{T} ≤ \textbf{150}). В последующих \textbf{T} строках задана очередная исходная Машина последовательность из кубиков. Длина последовательности не превышает \textbf{100}.
\OutputFile
Вывести искомое минимальное количество ходов, нужных Маше для получения палиндрома, либо, в случае невозможности сделать это, удивлённую фразу Маши "\textbf{Ooops...}" (без кавычек).
Giriş verilənləri #1
3 mamad asflkj aabb
Çıxış verilənləri #1
3 Ooops... 2