Şahmat#425
Bir çox idman yarışlarında rəqib komandaları və ya oyunçuları barışdırmaq üçün müxtəlif rituallar var. Bunlar əl sıxma, təzim və ya hətta şampan sıçratmaq ola bilər. ACM (Şahmat Ustaları Alyansı) öz rituallarını yaratmağı planlaşdırır: iki oyunçunun birlikdə oynadığı şahmat mini oyunu (adi qaydada bir-birinə qarşı deyil). Bu oyun 3 \times 3 ölçülü şahmat taxtasında keçirilir və hər bir oyunçu iki atla oyun aparır. Məqsəd, atları başlanğıc vəziyyətindən son vəziyyətə çatdırmaqdır. Gedişlər istənilən ardıcıllıqla edilə bilər (mütləq növbə ilə deyil). İki at eyni xanada ola bilməz.
Başlanğıc və son vəziyyətləri hakim müəyyən edir. Bəzi tapşırıqlar digərlərindən daha çətin, bəziləri isə hətta həllolunmaz ola bilər — beləliklə bəzən şahmat ustaları ritualları tamamlamaya bilərlər. Tapşırığınız, başlanğıc və son vəziyyətlər üzrə məsələnin həll olunub-olunmadığını və mümkün olduqda onu həll etmək üçün lazım olan minimal gediş sayını müəyyən edən proqram yazmaqdır.
Birinci sətrdə testlərin sayı verilir. Hər bir test sətirdən ibarətdir, hər sətr simvoldan ibarətdir. Hər sətrin ilk simvolu başlanğıc vəziyyətin müvafiq sətrini, aradakı boşluqdan sonra son simvol isə son vəziyyətin sətrini təsvir edir. Ağ at , qara at , boş xana isə (nöqtə) ilə göstərilir. Testlər bir-birindən boş sətirlə ayrılır.
Hər test üçün bir tam ədəd çıxarın — məsələnin çətinliyi. Əgər məsələnin həlli yoxdursa, çıxarın.
Nümunə 1