На шахматной тренировке для начинающих предложили такую задачу: нужно провести короля из левого верхнего угла доски в правый нижний за наименьшее количество ходов. При этом на закрашенные клетки ставить короля нельзя. Поле для задачи изображено на рисунке.

Лёша с задачей справился. Какое количество ходов он сделал? За один ход можно переместить короля в клетку, соседнюю с данной клеткой по стороне или вершине (если она не закрашена).
В качестве ответа укажите одно целое число.