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