Маша та паліндром
Маші у школі розповіли, що таке паліндром. І ось, прийшовши у гості до Міши, вона дістала його кубики, на яких зображені маленькі літери англійського алфавіту і почала грати сама з собою у гру, придуману по дорозі. Суть гри полягала у тому, що вона навмання складала слово-"абракадабру" із довільного числа кубиків, а потім пробувала отримати з цього слова паліндром.
Так як Маша ще маленька, то вона завбачливо у правилах гри вказала, що під час гри можна міняти місцями лише два сусідніх кубики. Звичайно, інколи їй це вдавалось, а інколи - ні, і тоді вона здивовано вимовляла "Ooops...".
Ваша задача знайти мінімальну кількість перестановок кубиків, потрібну Маші для отримання чергового паліндрому.
Вхідні дані
У першому рядку задано натуральне число - кількість тестових випадків T (T ≤ 150). У наступних T рядках задана чергова початкова Машина послідовність з кубиків. Довжина послідовності не перевищує 100.
Вихідні дані
Вивести шукану мінімальну кількість ходів, потрібну Маші для отримання паліндрому, або, у випадку неможливості це зробити, здивовану фразу Маші "Ooops..." (без лапок).