Ana və palindrom#1986
Anna məktəbdə palindromun nə olduğunu öyrəndi. Sonra, Benin evinə qonaq gedəndə, onun üzərində kiçik latın hərfləri olan bloklarını götürüb, yolda uydurduğu bir oyunu oynamağa başladı. Bu oyunda istənilən sayda kub istifadə edərək təsadüfi bir söz ("abracadabra") düzəldirdi və sonra bu sözü palindroma çevirməyə çalışırdı.
Ancaq Anna hələ balacadır, oyunun qaydalarına görə yalnız iki qonşu kubun yerlərini dəyişə bilir. Bəzən bu qayda ilə palindrom düzəldə bilirdi, bəzən isə alınmırdı və o zaman təəccüblə belə deyirdi: "Ooops..."
Sənin tapşırığın hər bir halda Annanın palindrom əldə etmək üçün minimum neçə qonşu dəyişmə (swap) əməliyyatı etməli olduğunu müəyyənləşdirmək və ya bunun mümkün olub-olmadığını tapmaqdır.
Birinci sətirdə təbii ədəd (T \leq 150) — testlərin sayı verilir. Sonrakı sətrin hər birində Annanın kubçalardan hazırladığı ilkin ardıcıllıq verilib. Ardıcıllığın uzunluğu -dən artıq deyil.
Hər test üçün Annanın palindrom əldə etmək üçün etməli olduğu minimal addımların sayını, əgər mümkün deyilsə, "Ooops..." (dırnaqsız) sətrini çap et.
Nümunə 1