Рабочее место участника

Играя в шахматы со Степаном Тимофеевичем, Хоттабыч иногда прибегал к колдовству, если положение на доске становилось угрожающим. Вот и на этот раз, у Хоттабыча, играющего черными, остались только король и конь. Он хочет переместить короля в другое более безопасное с его точки зрения место на доске. Хотя во время «бегства» белые фигуры остаются на своих местах, черный король не должен находиться на клетках, находящихся под боем (при необходимости конь может закрывать короля от удара), и черные не должны рубить белые фигуры. Степану Тимофеевичу, играющему белыми, кажется, что он делает ход, а на самом деле он ставит фигуру на прежнее место, но так долго продолжаться не может, поэтому желательно минимизировать количество ходов черных.

Ввод содержит 8 строк по 8 символов, описывающих начальную позицию. Символ '.' означает пустую клетку, прописные латинские буквы K, Q, R, B, N, P обозначают короля, ферзя, ладью, слона, коня и пешку белых соответственно. Строчные латинские буквы k и n обозначают короля и коня черных соответственно. Символ '@' обозначает желаемую позицию короля. Символы K, k, n и '@' встречаются во входных данных ровно один раз, символы Q, R, B, N, P – не более 3 раз. 8-я строка ввода соответствует первой горизонтали шахматной доски. В начальной позиции король черных может находиться под шахом.

Вывести одно число – минимальное число ходов черных для перемещения короля в новую позицию. Если переместить короля в новую позицию невозможно, то вывести число `-1`.

........
...k.@..
........
........
B.....n.
........
....Q...
...K....

4

........
..k..@..
........
........
......n.
........
...RR...
...K....

-1