Анна та паліндром#1986
Анна дізналася в школі, що таке паліндром. Згодом, у гостях у Бена, вона взяла його кубики з маленькими літерами латинського алфавіту і почала грати у гру, яку вигадала по дорозі. У цій грі вона навмання складала слово ("абракадабра") з будь-якої кількості кубиків, а потім намагалася перетворити це слово на паліндром.
Оскільки Анна ще маленька, правила її гри дозволяють під час гри лише міняти місцями два сусідні кубики. Іноді їй вдавалося отримати паліндром, а іноді — ні, і тоді вона з подивом вигукувала: "Ooops..."
Ваше завдання — визначити мінімальну кількість таких сусідніх перестановок, необхідних для того, щоб Анна отримала паліндром у кожному випадку, або з’ясувати, що це неможливо.
У першому рядку знаходиться натуральне число (T \leq 150) — кількість тестових випадків. У наступних рядках подано початкову послідовність з кубиків. Довжина послідовності не перевищує .
Для кожного тестового випадку виведіть мінімальну кількість перестановок, необхідних для отримання паліндрома, або, якщо це неможливо, виведіть "Ooops..." (без лапок).
Приклад 1