2. Rodný jazyk

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a, skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si sa naučiť, môžeš skúsiť našu KSP School.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi ([email protected]) alebo Ivke ([email protected]).

Dobrodruh Štepi sa rozhodol ísť na výpravu. Nechcel ísť sám, tak zo sebou zobral kuchárku Mišku, aby nehladovali. No a aby sa nenudili, išla s nimi aj papagáj Hanka. Nachystali sa, zbalili kopu vecí, veľa jedla, a vyrazili. Zopár dní sa túlali po pralesoch, keď zistili, že sa im míňajú zásoby jedla. Hanka vyletela nad stromy a v diaľke zbadala dedinu. Vydali sa smerom k nej a dúfali, že miestni budú priateľskí.

V dedine do ktorej Štepi dorazil mal však problém. Nevedel, ako komunikovať s domorodcami. Domorodci používajú zvláštny jazyk, v ktorom sa každá veta skladá z rôznej množiny znakov bez medzier. Aby to nebolo dosť zvláštne, vedia ich vnímať iba ak sú v podobe palindrómov. Ak by im Štepi povedal niečo čo nie je palindróm, začali by sa naňho ozaj škaredo a nechápavo pozerať a to on nerád.

Štepi by s nimi chcel vedieť komunikovať, no sám to nezvládne, nakoľko má žiaľ aibofóbiu (fóbiu z palindrómov). Potreboval by preto od teba pomoc s komunikáciou s domorodcami.

Úloha

Štepi by chcel domorodcom povedať \(T\) viet, pre ktoré už má množiny znakov priparvené. Od teba potrebuje, aby si ich naformuloval/a do palindrómov. Je však možné, že urobil chybu, a v tom prípade sa palindróm vytvoriť nedá. Ak na takú vetu narazíš, daj mu vedieť.

Formát vstupu

Na prvom riadku dostaneš jedno číslo \(T\) (\(1 \leq T \leq 2000\)) označujúce počet viet, ktoré Štepi potrebuje naformulovať. Nasleduje \(T\) dvojíc riadkov. Na prvom riadku z dvojice je číslo \(1 \leq N \leq 10^5\) udávajúce počet znakov vo vete a na druhom riadku z dvojice je nenaformulovaná veta, skladajúca sa z \(N\) znakov malej anglickej abecedy.

Exituje 5 sád vstupov, každá za 20 bodov. V jednotlivých sadách platia nasledovné obmedzenia:

Formát výstupu

Pre každú vetu vypíšte na zvlášť riadok jej formuláciu v podobe palindróm, prípadne ak sa nedá naformulovať do podoby palidnrómu, vypíšte CHYBA.

Ak existuje viacero spôsobov naformulovania vety, vypíšte ľobovoľný z nich.

Príklad

Input:

5
5
abbaa
4
abbb
6
zxyxxz
10
apkrrsapsk
11
mpfsxkmskpf

Output:

ababa
CHYBA
CHYBA
praskksarp
fkmspxpsmkf

Prvú vetu by sme mohli naformulovať napr. aj ako baaab. Podobne to platí aj pre ostatné vety, ktoré sa dajú naformulovať ako palindróm.