珅泽教育的刘老师正在准备一项寻路实践，他请小珅完成下面的任务。

给定一个 $N\times N$ 的棋盘。字符 K 表示骑士起点，字符 . 表示可落脚格，字符 # 表示不能落脚的障碍。骑士每次必须按国际象棋规则移动：一个方向走两格，再在垂直方向走一格。

请计算骑士到达左上角格 $(1,1)$ 的最少跳跃次数；若无法到达，输出 $-1$。

输入格式

第一行输入 $N$。

接下来 $N$ 行输入棋盘。

输出格式

输出到左上角的最少跳跃次数，无法到达输出 -1。

4
..#.
....
....
...K

2

5
.....
.....
....#
.....
.K...

3

6
..#...
......
.#....
......
.#...#
...K..

4

数据范围与约定

• $1 \le N \le 1000$
• 棋盘中恰有一个 K