Mifik şahmatlar
Dostunuz Vasya "Mifik Şahmat" adlı bir kompüter oyunu hazırlayır. Layihəni vaxtında tamamlaması üçün köməyə ehtiyacı var.
Vasya dostlarından yardım istədi. Ona fiqurların bir xanadan digərinə optimal yollarla hərəkət etməsini hesablayan bir modul lazımdır. Vasya'nın çox dostu olduğu üçün hər birinə kiçik bir alt tapşırıq verildi. Sizin vəzifəniz, kentavrın bir xanadan digərinə çatması üçün lazım olan minimal gediş sayını müəyyən edən bir proqram yazmaqdır.
Mifik şahmat 9x9 ölçülü bir şahmat taxtasında oynanılır və künc xanalari qara rəngə boyanmışdır. Kentavr - mifik şahmat fiqurudur, at və filin xüsusiyyətlərini birləşdirir. Kentavr ağ xananın üzərində durduqda yalnız at kimi, qara xananın üzərində durduqda isə yalnız fil kimi hərəkət edə bilər. Şəkillərdə iki kentavr üçün hərəkət variantları göstərilmişdir (kentavrın mövqeyi "K" hərfi ilə, hərəkət edə biləcəyi xanalarsa ulduzlarla işarələnmişdir).
Giriş verilənləri
Giriş faylında birinci sətirdə təbii ədəd N - testlərin sayı qeyd olunub. Növbəti N sətirdə hər bir test üçün mifik şahmat taxtasının iki xanalarının koordinatları (böyük latın hərfi və rəqəm) boşluqla ayrılmış şəkildə qeyd olunub.
Çıxış məlumatları
Hər bir test üçün kentavrın birinci xananın üzərindən ikinci xananın üzərinə çatması üçün lazım olan minimal gediş sayını ehtiva edən sətir çıxarılır. Əgər çatmaq mümkün deyilsə, onda "-1" (tırnaqsız) çıxarılır.