Şahmat
Bir çox idman yarışlarında rəqib komandaları və ya oyunçuları barışdırmaq üçün müxtəlif rituallar mövcuddur. Bunlar əl sıxma, təzim və ya hətta şampan sıçratma ola bilər. ACM (Şahmat Ustaları Alyansı) öz rituallarını yaratmağı planlaşdırır və bunun üçün şahmat mini oyunu təşkil edir. Bu oyunda iki oyunçu bir-biri ilə ittifaqda iştirak edir (adi qaydada bir-birinə qarşı deyil). Oyun 3x3 ölçülü şahmat taxtasında keçirilir, hər bir oyunçunun iki şahmat atı var və onlar bir mövqedən digərinə keçməlidirlər (oyunçular gedişləri istənilən ardıcıllıqla edə bilərlər, mütləq növbə ilə deyil). Bu zaman iki at eyni xanada ola bilməz.
Başlanğıc və son mövqelər hakim tərəfindən müəyyən edilir. Məlum olur ki, bəzi belə məsələlər digərlərindən daha çətindir və bəziləri hətta həll olunmaz ola bilər - buna görə də bəzi oyunçular bəzən ritualları tamamlaya bilmirlər. Sizin vəzifəniz verilmiş başlanğıc və son mövqelərə əsasən oyunun uğurla başa çatdırılmasının mümkünlüyünü müəyyən edə bilən və uğur halında məsələnin çətinliyini - məsələnin həlli üçün lazım olan minimal mümkün gediş sayını müəyyən edə bilən proqram yazmaqdır.
Giriş verilənləri
Bir neçə testdən ibarətdir, hər birində 3 sətir və 7 simvol var. Hər sətirin ilk 3 simvolu başlanğıc mövqeyinin müvafiq sətirini təsvir edir, sonra boşluq gəlir və son 3 simvol eyni şəkildə son mövqenin sətirini təsvir edir. Ağ at «W» simvolu ilə, qara at isə «B» simvolu ilə göstərilir, boş xanalar «.» (nöqtə) ilə göstərilir. Test halları bir-birindən boş sətirlə ayrılır. Testlərin sayı ilk sətirdə göstərilir.
Çıxış verilənləri
Hər bir test üçün bir tam ədəd çıxarın - məsələnin çətinliyi. Əgər məsələnin həlli yoxdursa, -1 çıxarın.