Böyük ölçülü pancake çevricisi
Keçən il Sonsuz Pancake Evi yeni bir pancake növü təqdim etdi. Pancake-in bir tərəfində şokolad qırıntılarından xoşbəxt üz ("xoşbəxt tərəf"), digər tərəfində isə heç nə yoxdur ("boş tərəf").
Bu gün siz baş növbətçi aşpazsınız. Pancake-lər isti səthdə bir sırada hazırlanır. Effektivliyi artırmaq üçün Sonsuz Pancake Evi sizə dəqiq k ardıcıl pancake-i çevirə bilən iri ölçülü pancake çevirici təqdim etdi. Yəni, ardıcıl yerləşən k pancake üçün hər bir xoşbəxt tərəfli pancake-i boş tərəfli pancake-ə və əksinə dəyişir. Pancake-lərin soldan sağa olan sırası dəyişmir.
Siz çevirici ilə k-dan az pancake çevirə bilməzsiniz, hətta sıranın sonunda belə (çünki bişirmə səthinin hər iki tərəfində qabarıq kənarlar var). Məsələn, ilk k pancake-i çevirə bilərsiniz, amma ilk k - 1 pancake-i çevirə bilməzsiniz.
Hələ də işin incəliklərini öyrənən şagird aşpazınız bir neçə ayrı pancake-i çevirmək üçün köhnə üsulla pancake çeviricisini istifadə etdi və sonra müştərilər mətbəxə gəlməyə başlamazdan əvvəl tualetə qaçdı. Sizdə yalnız iri ölçülü pancake çevirici qalıb. Onu tez bir zamanda istifadə etməlisiniz ki, bütün pancake-lər xoşbəxt tərəfi yuxarı çevrilsin. Beləliklə, müştərilər ziyarətlərindən məmnun qalacaqlar.
Verilmiş pancake vəziyyətinə görə, bütün pancake-ləri xoşbəxt tərəfi yuxarı çevirmək üçün lazım olan minimum iri ölçülü pancake çevirici istifadəsini hesablayın və ya bunun mümkün olmadığını göstərin.
Giriş məlumatları
Birinci sətir testlərin sayı t (1 ≤ t ≤ 100) ehtiva edir. Sonra t test gəlir. Hər bir test bir sətir s və tam ədəd k (2 ≤ k ≤ s uzunluğu) ehtiva edir. s pancake sırasını təyin edir: hər bir simvol ya + (pancake xoşbəxt tərəfi yuxarıdır) ya da - (pancake boş tərəfi yuxarıdır).
Çıxış məlumatları
Hər bir test üçün Case #x: y sətirini çıxarın, burada x testin nömrəsidir (1-dən başlayaraq) və y ya bütün pancake-ləri xoşbəxt tərəfi yuxarı çevirmək mümkün olmadıqda IMPOSSIBLE, ya da məqsədə çatmaq üçün çeviricinin ən az istifadə sayıdır.