Kate is stuck in a maze. You should help her to find her way out.
On the first line, you will be given how many rows there are in the maze. On the following n lines, you will be given the maze itself. Here is a legend for the maze:
•	"#" - means a wall; Kate cannot go through there
•	" " - means empty space; Kate can go through there
•	"k" - the initial position of Kate; start looking for a way out from there
There are two options: Kate either gets out or not:
•	If Kate can get out, print the following:
"Kate got out in {number_of_moves} moves".
Note: If there are two or more ways out, she always chooses the longest one.
•	Otherwise, print: "Kate cannot get out".

Input
4
######
##  k#
## ###
## ###

Output:
Kate got out in 5 moves