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