Давним давно, Король Артур та Лицарі Круглого Столу збирались на Новий рік, щоб відсвяткувати свою дружбу. У пам'ять про ці події розглянемо настольну гру Камелот для одного гравця, у якій фігура Короля та декілька фігур Лицарів довільним чином розміщені у різних клітинках дошки.
Дошка має розмір 8х8 клітинок (рис.1).
Рис. 1. Дошка
Король може переміщувтись у довільну суміжну клітинку дошки, як показано на рис.2, якщо при цьому він не виходить за межі дошки.
Рис. 2. Усі можливі переміщення Короля
Лицар може переміщуватись так, як показано на рис.3, якщо при цьому він не виходить за межі дошки.
Рис. 3. Усі можливі переміщення Лицаря
Під час гри гравець може помістити більше однієї фігури у одну клітинку. Клітинки вважаються достатньо великими і не виникає перешкод для вільного переміщення фігур.
Гравцю необхідно так переміщувати фігури Короля та Лицарів, щоб зібрати їх в одній клітинці за найменше число ходів. Ходи фігурами необхідно робити за правилами, описаними вище. Додатково, якщо Король та один чи більш Лицарів знаходяться у одній клітинці, гравець може перемістити Короля та одного з Лицарів разом за правилами переміщення Лицаря і вважати це одним ходом.
Напишіть програму для обчислення мінімальної кількості ходів, необхідних для переміщення усіх фігур у одну клітинку дошки.
Вхідний файл містить один рядок символів, які описують початкове розміщення фігур на дошці. Рядок містить послідовність клітинок дошки, перша з яких – клітинка Короля, інші – клітинки Лицарів (кількість Лицарів не більше 63). Кожну клітинку описано парою буква-цифра. Буква позначає горизонтальну, а цифра – вертикальну координату клеітинки дошки. Усі фігури на початку гри розміщено у різних клітинках.
Вихідний файл повинен містити єдиний рядок з додатнім цілим числом, яке позначає мінімальне число ходів гравця, необхідних для переміщення усіх фігур в одну клітинку дошки.